自动搬运

查看原文

来自洛谷，原作者为

	Aamumatematiikka The last dance...

搬运于2025-08-24 23:16:41，当前版本为作者最后更新于2025-05-25 15:40:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

拿到题目我们可以注意到点 $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)$。