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

关于精度的给后来人一点建议

Posted by liurui39660 at 2016-07-31 12:01:10 on Problem 1755
最后判断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:
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