题解：P12596 测速仪惊吓

· · 题解

拿到题目我们可以注意到点 P 一定在这个凸包的内部，所以可以把这个凸包看作是许多个三角形拼成的，底为凸包的边，定点为 P。

我们先利用向量的叉积预处理出每个小三角形的面积的 2 倍，然后对这个序列进行双指针搜出连续的一部分使选中的和剩下的只差最小。

双指针的具体过程：

当选中区间的值没有到达 \frac{sum}{2} 时，不断向右拓展，达到 \frac{sum}{2} 后右移左端点缩小范围，继续搜下一个临界值。

由于是环形，所以可以将序列复制一遍。

代码如下：

#include <iostream>
using namespace std;
typedef long long ll;
const ll N=200005, INF=0x3f3f3f3f3f3f3f3f;
ll n, x[N], y[N], xp, yp, a[N], sum=0, tot=0, ans=INF;
ll S(ll a, ll b){
    return (x[a]-xp)*(y[b]-yp)-(y[a]-yp)*(x[b]-xp);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
    scanf("%lld%lld",&xp,&yp);
    for(ll i=1;i<n;i++) sum+=a[i]=S(i,i+1);
    sum+=a[n]=S(n,1);
    for(ll i=n+1;i<=2*n;i++) a[i]=a[i-n];
    for(ll l=1,r=1;l<=2*n;tot-=a[l++]){
        while(2*tot<sum&&r<=2*n) tot+=a[r++];
        ans=min(ans,min(abs(2*tot-sum),abs(2*(tot-a[r-1])-sum)));
    }
    return printf("%lld",ans)&0;
}

预处理复杂度为 O(n)，双指针只用搜一遍，复杂度为 O(n)，总复杂度为 O(n)。