[ICPC2021 Macao R] Laser Trap 题解

SDLTF_凌亭风 · 2023-09-24 18:34:38 · 题解

我超！计算几何！

先进行一次极角排序，然后用双指针找最小删除量即可。

注意，如果你使用化环为链，空间记得开两倍，否则喜提 RE。

cin >> n;
for(int i = 1; i <= n; ++ i) cin >> pts[i].x >> pts[i].y;
sort(pts + 1, pts + 1 + n);
for(int i = 1; i <= n; ++ i) pts[i + n] = pts[i]; // 化环为链
for(int i = 1; i <= n;) {
    for(int j = i + 1; j <= n; ++ j) if (!(pts[i] == pts[j])) break;
    nxt[i] = j, nxt[n + i] = n + j;
    i = j;
}
int res = n;
for (int i = 1, j = 1; i <= n; i = nxt[i]) { // 双指针
    while (j < n + i && (i == j || check(pts[i], pts[j]))) j = nxt[j];
    res = (j == n + i) ? 0 : min(res, j - nxt[i]);
}
cout << res << '\n';