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

给后来人一点建议 尤其是那些莫名奇妙就WA的

Posted by liurui39660 at 2016-07-30 01:49:57 on Problem 3525 and last updated at 2016-07-30 01:56:18
1.数组一定要大,因为中间每有一个点在半平面外部时,最多可以造出两个新的交点,开到100显然不够,根据当年的比赛的测试数据,最少需要开到254,poj可能改过数据,有人200也能过
2.求交点一定要精准,主要是针对那些没有看过黑书和蓝白书的同学,还有额自己,不要列点斜式求方程解出交点坐标,浮点误差会迅速累积,并且当数据规模较大时会对最后几次二分产生巨大影响,使得结果的误差被扩大到1e-3级甚至更大,不WA怎么可能

下面是两条小小的剪枝建议,写给对边界处理略有茫然的同学
3.二分的上下界选取要明智,下界选0没办法,但上界从5002开始足矣,因为题目规定的坐标范围是10000*10000,在此范围内画圆,半径最大也只有5000.00000,再大一点意义都没有,虽然这不会导致WA也不会导致TLE,但是少算几次终究会让人心里舒坦
4.二分的结束条件不宜过小,如题目所言,只要精确到1e-5即可(额就写的1e-5),如果要保险,写成1e-6足矣,再精确也只是浪费计算机资源而已,既显示不出来,更没有实际意义,而且会更易受到扰动,出现意料外的状况
5.没有添加临界边的需要,虽说为防止出现图形不封闭的情况会人为添加4条坐标极大的边,但是在这种题里完全没有这个必要,因为能影响到二分的,只是最后点集是否为空,额外添加这4条边,除了会增加一些不必要的代码,而且会给代码维护带来一点点麻烦

最后要说,题目真的不难,只要知道如何求偏移量,实现上细心一些,其实1A并不难(然而额并没有做到)

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