自动搬运

查看原文

来自洛谷，原作者为

	SDLTF_凌亭风 人生的相遇相逢不存在 O(1)，愿每位 OIer 仍在路上

搬运于2025-08-24 22:50:30，当前版本为作者最后更新于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';