P9658 [ICPC2021 Macao R] Laser Trap题解

rzm120412 · 2023-09-29 13:36:21 · 闲话

几何题！！！极角排序！！！

题意：二维平面上 n(n \ge 10^{6}) 个点，第i个点 (xi,yi) (-10^{9}\ge x,y\ge10^{9}) ，保证不存在两点和 (0,0) 共线任意两点之间都有一条连线，若干条连线将 (0,0) 围住在封闭图形里求最少删掉多少个点，使得 (0,0) 能逃脱连线的围困，也即和无穷远是连通的。

思路：考虑逃脱围困时剩下的点的情况，剩下的点一定在某个 \ge 179 度的半平面内，所以四象限极角排序后，枚举半平面一侧的点，双指针找到另一侧最远的点遍历一圈更新答案，排序后二分也可以。

代码和一楼的差不多，不放了。