别样的凸包大战

CleverSea · 2025-07-08 21:56:13 · 题解

别样的凸包大战

一天，仵沉蛋给我打来电话。他说：“你敢不敢和我举行凸包大战？”我豪爽的答应了：“我当然敢！周日下午在 xx 路 xx 大厦给定 n 个点的凸包和内部点 P，选两个顶点分割凸包，求出最小面积差的两倍，谁不来谁就是怂货。”

我原本以为我恐吓了仵沉蛋，仵沉蛋应该躲在家，不敢找我，便用 O(n^2) 暴力枚举尝试秒杀，可正当这时，我听到了音乐声，原来是评测系统跳出了 TLE。一看数据规模，n \le 10^5！仵沉蛋打来电话："小废物，前缀和都不会用？再不会就退役吧！"我回击道："我要用叉积和二分查找优化，把你 hack 掉，你说好不好啊？"

他吓得没再回应我，可是到了周日，仵沉蛋竟然又给我打电话了，他还真要和我举行凸包大战，于是我按照约定，到达了 xx 大厦，可他已经等我很久了。

第一回合，我占据上风。发现凸包分割的核心性质：设总面积为 S，分割后面积差为 |2S_1 - S|。用叉积计算时，所有面积值都是整数。我快速写出核心逻辑：

long long dx1 = Q[i-1].x - P.x;
long long dy1 = Q[i-1].y - P.y;
long long dx2 = Q[i].x - P.x;
long long dy2 = Q[i].y - P.y;
long long cross_val = dx1 * dy2 - dy1 * dx2;

等我已建好前缀和数组 pre（pre[i] = \sum_{k=1}^{i} (Q_k-P)\times(Q_{k-1}-P)）时，仵沉蛋还在手算叉积，他比不过我，到了第六回合，他就主动认输了。

第二局，他开始占上风，将凸包点复制：

for (int i = 0; i < n; i++) Q[i+n] = Q[i];

我也不甘势弱，但我由于轻敌，直接枚举点对，遭到仵沉蛋冷笑："环形结构都不处理？"我们僵持了上百回合，最终我因未处理环形边界败北。

从那时起，我不再轻敌。认真研究后得出一套绝杀方案：

计算凸包总面积 total\_T = pre[n]。
对每个起点 i，计算关键值 D = 2\times pre[i] + total\_T。
在区间 [i+1, i+n-1] 二分查找 j 满足 2\times pre[j] \geq D。

while (l <= r) {
    int mid = (l+r)/2;
    if (2*pre[mid] >= D_val) j0 = mid, r = mid-1;
    else l = mid+1;
}

用 j_0 和 j_0-1 更新最小面积差。

第二天，我们举行第三局，他使出祖传 O(n^2) 暴力，对我发起了猛烈的攻击。我们势均力敌，平分秋色，n \le 10^5 的数据让我们比了3个多小时，也没分出胜负。

后来，他不知不觉的睡着了，我趁着这个好机会，一记凌车漂移，环形复制避开车祸现场：

for (int i=0; i<n; i++) Q[i+n] = Q[i];

一飞冲天，二分查找精准定位分割点：

int l = i+1, r = i+n-1;
while (l <= r) { /* 二分过程 */ }

最终计算 ans = \min( |2\times pre[j_0]-D|, |2\times pre[j_0-1]-D| )，打得他不敢还手，对他的打击比#define int long long之后没有把int main()改成signed main()还大。

Code

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int N = 200000; // 最大点数：100000 * 2

struct Point {
    long long x, y;
};

Point Q[2 * N];      // 凸包点（复制成2倍）
Point P;             // 内部点
long long pre[2 * N + 10]; // 前缀和数组

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // 读入凸包点
    for (int i = 0; i < n; i++) {
        cin >> Q[i].x >> Q[i].y;
    }
    // 复制凸包点（环形处理）
    for (int i = 0; i < n; i++) {
        Q[i + n] = Q[i];
    }
    // 读入内部点P
    cin >> P.x >> P.y;

    // 计算前缀和数组 pre[0..2*n]
    pre[0] = 0;
    for (int i = 1; i <= 2 * n; i++) {
        // 向量 PQ[i-1] 和 PQ[i] 的叉积
        long long dx1 = Q[i - 1].x - P.x;
        long long dy1 = Q[i - 1].y - P.y;
        long long dx2 = Q[i].x - P.x;
        long long dy2 = Q[i].y - P.y;
        long long cross_val = dx1 * dy2 - dy1 * dx2;
        pre[i] = pre[i - 1] + cross_val;
    }
    // 整个凸包的2倍面积
    long long total_T = pre[n];
    // 初始化答案为极大值
    long long ans = (1LL << 62);

    // 枚举起点 i
    for (int i = 0; i < n; i++) {
        // 计算 D_val = 2*pre[i] + total_T
        long long D_val = 2 * pre[i] + total_T;
        int left_index = i + 1;
        int right_index = i + n - 1;

        // 二分查找第一个满足 2*pre[j] >= D_val 的位置 j0
        int l = left_index, r = right_index;
        int j0 = right_index + 1; // 初始化为区间外
        while (l <= r) {
            int mid = (l + r) / 2;
            if (2 * pre[mid] >= D_val) {
                j0 = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        long long min_diff = (1LL << 62); // 当前 i 的最小差值

        // 检查位置 j0
        if (j0 >= left_index && j0 <= right_index) {
            long long val = 2 * pre[j0] - D_val;
            if (val < 0) val = -val;
            if (val < min_diff) min_diff = val;
        }
        // 检查位置 j0 - 1
        if (j0 - 1 >= left_index && j0 - 1 <= right_index) {
            long long val = 2 * pre[j0 - 1] - D_val;
            if (val < 0) val = -val;
            if (val < min_diff) min_diff = val;
        }

        // 更新全局答案
        if (min_diff < ans) {
            ans = min_diff;
        }
    }

    cout << ans << endl;

    return 0;
}

时间复杂度 O(n \log n)。