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

这道题又加深了对KM的理解,简要说说这道题的坑

Posted by 1593767536 at 2018-03-02 16:20:03 on Problem 3565 and last updated at 2018-03-02 16:24:44
1.不能为了省精度就用距离的平方代替距离,这道题能用KM在于四边形不等式的几何形式dist
(A,B)+dist(C,D)>dist(A,C)+dist(B,D),其中ABCD是四边形,证明利用对角线交点O与AB,
CD两条边构成的三角形不等式证明,即OA+OB>AB,OC+OD>CD,两式相加得到AC+BD>AB+CD,对于
平方没有三角形不等式,事实上可以构造使AB*AB+CD*CD=AC*AC+BD*BD,比如这组数据:
3
-8 -1
-8 -7
0 8
-5 -8
-4 -8
-8 8
2.注意精度问题,这不用多说了,用到double的地方都要注意。
3.TLE问题,只用一个变量代替sl数组会造成TLE,因为它实际上减小了每次应该减掉的d值,使
用标准的sl数组才能保证复杂度正确

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