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 darkforte at 2014-08-25 10:52:30 on Problem 1228 and last updated at 2014-08-25 10:54:03
我的做法就是将所有点逆时针排序,然后检查是否有两个连续的拐角就可以了。

我一开始的做法是从第一个点开始排,假设一下之前的向量是(1,0),
然后依次检查每一个没有被排序的点,选取一个夹角最小的(利用点积除以模之积判断),
夹角一样时选择距离最小的,然后排序进来,并更新现在的向量。

这样由于第一个点的位置不同,排出来有可能是顺时针,有可能是逆时针,但是我觉得这应该没关系啊……就一直WA,今早我加了一段话,排序之前先找到最左下角的点,就AC了……

求一组数据卡掉我之前的算法……

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