Detail of message

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

一直没发现会退化。。。TLE无数次...

Posted by ArXoR at 2006-12-24 21:30:18
In Reply To:Orz !!! 确实是这样的 Posted by:Ikki at 2006-12-24 07:40:37

Followed by:

哪里退化？ (66) wywcgs 2006-12-24 23:42:02
- n个相同的点的时候，不特判的话会退化成O(n^2*logn)，至少我的算法现在会这样 (74) ArXoR 2006-12-25 11:59:05
  - 哦？难道不是和最近点对一样检查后7个吗？ (60) wywcgs 2006-12-25 12:14:00
    - faint。这个结论貌似是错的 (39) wywcgs 2006-12-25 12:25:27
      - p>0时，点的密度是有常数上限的，但是全相同的时候p==0就会有O(n)个。。。所以退化，不过是可以规范地避免的 (45) ArXoR 2006-12-25 12:47:20
        嗯。我是说那个7是不对的 (26) wywcgs 2006-12-25 12:52:10
        常数是16个，检查[-d/2,d/2]之间的区间 (32) Ikki 2006-12-25 17:03:31
re (0) sunmoonstar 2006-12-24 23:59:09
re (0) sunmoonstar 2006-12-24 23:59:13
re (0) sunmoonstar 2006-12-24 23:59:19

Post your reply here:

Home Page Go Back To top

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