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 |
关于精度的给后来人一点建议最后判断yes或no普遍方法就两种,其一是判断最后半平面围成的面积的大小,其二是判断最后半平面中剩余的点的个数,对这两种方法,所需要的精度值(EPS)是不同的 对于算面积的,由于最后一组数据2 1 1 10000 2 2 9999中第一个人最后半平面交围成的面积大小是2e-16,因而精度必须达到1e-16级才能将其视为存在可行域,从这一点上,精度确实要求较高 但对于按剩余点数计算的,想必前面一定有一个剪枝,就是判断A,B,C的值和0的关系,或者说能否找到一个人比当前考虑的人的三项速度都要快(或相等),如果没有这个剪枝,在倒数第2组数据中由于每个人的速度都非常接近,很难不WA,而这个剪枝需要的精度并不是很大,1e-8级足矣 倒数第2组数据到底有多么奇葩?所有人的所有速度都在9997到10000范围内浮动之间,而且总人数也不少 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator