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 |
这道题又加深了对KM的理解,简要说说这道题的坑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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator