Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

O(n^2/2*logn),500多毫秒过 (用G++提交400+MS)......

Posted by duanxian0621 at 2011-09-15 22:13:42 on Problem 2780 and last updated at 2011-09-16 16:09:13
Accepted  208K  532MS  C++  761B   (用G++提交400+MS)
这道题应该是有很多组测试数据吧,所以要尽量减少不必要的操作,即使多一个+n的复杂度都要耗费很多时间,同样的排序比较斜率的方法,(n^2/2)*logn时间是500+Ms,而n^2*logn耗时竟达到1100+MS,可见应该有大量测试数据 。 一开始利用直线方程三元素+gcd同样的n^2logn+n^2的复杂度因为操作比较多就TLE。改为基础的直接排序比较斜率就AC!

排序比较斜率的思路:对于一条直线上覆盖的点的个数。共n个点,从每个点出发,以点a(x,y)为例,后面与它相连的点得到的直线的斜率全部求出(注:当x[j]-x[i]==0时,斜率赋为无穷大),排序后求出斜率相同出现最多的那个,即为过当前a(x,y)这个点的直线中所覆盖的点的个数最多的那条直线(确定斜率及直线过得某个点,这条直线也就确定了),对其他的点也做同样处理。则可求出所有的直线中覆盖点最多的那个了。
一点见解,大牛莫笑,望指教!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator