POJ1106极角排序
题目
给出若干个点和一个半圆,半圆可以绕着圆心任意旋转,问最多能覆盖多少个点。
解题思路
距离圆心的距离大于半径的点可以直接先排除掉。
将剩余的点进行极角排序,然后用一个双端队列维护能被半圆覆盖的点,当队首和当前处理点的角度大于$\pi$时,弹出队首元素。期间队列最大的size就是答案。
需要注意的是,当前处理点极角接近$\pi$时,最开始邻近$-\pi$处的点也会有贡献,可以将所有点复制一份加到后面,并将复制的点极角加上$2\pi$。
时间复杂度$O(nlogn)$。比网上的很多题解更优。
代码
G++死活过不去
1 |
|