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 |
没有写凸包,就写了个逆时针排序,但是不知道为什么必须先找到最左下角的点?我的做法就是将所有点逆时针排序,然后检查是否有两个连续的拐角就可以了。 我一开始的做法是从第一个点开始排,假设一下之前的向量是(1,0), 然后依次检查每一个没有被排序的点,选取一个夹角最小的(利用点积除以模之积判断), 夹角一样时选择距离最小的,然后排序进来,并更新现在的向量。 这样由于第一个点的位置不同,排出来有可能是顺时针,有可能是逆时针,但是我觉得这应该没关系啊……就一直WA,今早我加了一段话,排序之前先找到最左下角的点,就AC了…… 求一组数据卡掉我之前的算法…… Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator