Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
O(n^2/2*logn),500多毫秒过 (用G++提交400+MS)......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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator