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 |
Re:雁过留声——排序+扫描In Reply To:雁过留声——排序+扫描 Posted by:fanhqme at 2009-08-25 14:53:10 为什么不用叉积? > 这题我的算法是比较保守的: > 枚举一个点作为起点,让所有在它右边的点和它连线,然后按斜率排序, > 最后计数。 > > 一个比较关键的问题卡住了我很久: > 如何进行斜率排序? > 几个特例: > 1.无斜率 > 2.两个斜率为2100000000/2100000001和2099999999/2100000000的线段似乎无法用double区分得很清楚。 > > 这时,我猛然想到了一个问题: > 什么是排序? > 一种解释:把所有的数从大到小存进数组里 > 另一种解释:一系列对象根据某种偏序集关系计算次序 > > 既然用double排序斜率有风险,那么不妨: > 把所有直线的斜率写成分数的形式:p/q,如果没有斜率,则写1/0或-1/0 > > 然后,按斜率的分子排序,如果相同,在按分母排序。 > 貌似得到的结果不是按斜率大小排的序,但是: > 它保证了相同的数排到了相邻的位置! > > 对于这题,这个性质足以。 > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator