Skip to content

Latest commit

 

History

History

587.Erect-the-Fence

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

587.Erect-the-Fence

此题的本质就是根据一群点,找出覆盖全部点的凸多边形。

首先,将所有点按从左到右、从低到高排序。

先考虑凸多边形的下边界。在hull_lower先入列points[0]。假设已经在hull_lower队列里有C,D两点,则考察points[i]作为候选点X,我们判断CD和DX两条矢量的夹角是否是凸的(即DX相对于CD是往上翘的)。如果是的话,则将X加入队列作为E;不是的话,则我们将D踢出队列,再查看此时队列末尾的B、C和X点的关系,以此类推,直至满足三点成凸,或者队列中只剩一个(最左下角的初始点),就不再踢了,直接将X加入。

考虑凸多边形的上边界,用类似的方法。在hull_upper先入列points.back()。然后在points里倒序遍历所有点,依然要保证所有入列的点,满足三点成凸的关系。

最后,将hull_lower和hull_upper归并至一处,去除掉重复的点,就是所求凸多边形的边界点。

注:向量a=(x1,y1),b=(x2,y2),则叉乘axb=(x1y2-y1x2)表示一个朝向z方向的向量。如果为正,则说明从a到b转过了一个逆时针的角度;如果为负,则说明从a到b转过了一个顺时针的角度。这可以用右手螺旋定则来记忆。