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

Re:雁过留声——排序+扫描

Posted by tjbwyk at 2011-06-08 01:05:53 on Problem 1118 and last updated at 2011-06-08 01:06:42
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:
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