自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

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

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

以下是正文

Solution

和 这道题 几乎一模一样。

问题转化为：给你一组向量 $a$，请你分配一个权值 $w_i \in \{-1,0,1\}$，最大化 $|\sum w_ia_i|$ 的值。

设最终的向量和是 $v$。

显然不存在和 $v$ 垂直的向量。和它夹角小于 $90$ 度的选上一定更优，大于 $90$ 度的选相反数一定更优。

结论也和那道题一模一样了，极角排序之后跑一个双指针即可。注意特判向量贡献的情况（需要算出是同向还是反向。）

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200000+10;
int n,x[MAXN],y[MAXN];
int gid(pair<int,int> p) {
	if(p.first>0&&p.second>=0) return 1;
	if(p.first<=0&&p.second>0) return 2;
	if(p.second<=0&&p.first<0) return 3;
	return 4;
}
int solve(int sx,int sy,int tx,int ty) {
	int px=sx-tx,py=sy-ty;
	tx-=px,ty-=py;
	return tx*tx+ty*ty;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	vector<pair<int,int>> vc;
	ffor(i,1,n) {
		cin>>x[i]>>y[i];
		if(x[i]!=0||y[i]!=0) vc.push_back({x[i],y[i]});
	}
	sort(vc.begin(),vc.end(),[](pair<int,int> A,pair<int,int> B) {
		if(gid(A)!=gid(B)) return gid(A)<gid(B);
		return A.first*B.second>A.second*B.first;
	});
	n=vc.size();
	ffor(i,1,n) x[i]=vc[i-1].first,y[i]=vc[i-1].second;
	int pos=1,sx=0,sy=0,tx=0,ty=0,ans=0;
	ffor(i,1,n) sx+=x[i],sy+=y[i];
	tx=x[1],ty=y[1];
	ans=max(ans,sx*sx+sy*sy);
	ffor(i,1,n) {
		ans=max(ans,solve(sx,sy,tx,ty));
		if(x[i]*y[i%n+1]-y[i]*x[i%n+1]<0||x[i]*y[i%n+1]-y[i]*x[i%n+1]<0&&(x[i]*x[i%n+1]<0||y[i]*y[i%n+1]<0)) {pos=i%n+1,tx=x[pos],ty=y[pos];continue ;}
		while(pos%n+1!=i&&(x[i]*y[pos%n+1]-y[i]*x[pos%n+1]>0||x[i]*y[pos%n+1]-y[i]*x[pos%n+1]==0&&x[i]*x[pos%n+1]>=0&&y[i]*y[pos%n+1]>=0)) {
			pos=pos%n+1;
			tx+=x[pos],ty+=y[pos],ans=max(ans,solve(sx,sy,tx,ty));
		}
		tx-=x[i],ty-=y[i],ans=max(ans,solve(sx,sy,tx,ty));
	}
	cout<<ans; 
	return 0;
}