自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

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

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

以下是正文

Solution

典题，似乎做过。

结论：必定能找到一条直线，使得选取这条直线某一侧的所有点达到答案最大。（严格意义上同一侧，这条线上的点不选）

假设最终的向量是 $\vec v$，我们取垂直于它的直线 $l$。显然不可能有向量严格与 $l$ 重合，否则随便调整会使长度增加；如果 $l$ 和 $\vec v$ 同侧有一个向量没有被选中，选上他会让 $\vec v$ 增加，矛盾；如果 $l$ 和 $\vec v$ 异侧有一个向量被选中了，将他取反就相当于撤销，这时候发现也是不优的。

如何找到 $l$？

一种想法是直接随机化，我不是很懂其正确性。

确定性做法是考虑双指针，将向量极角排序后维护两个指针 $l$ 和 $r$，使得排序后的第 $l$ 个向量和第 $r$ 个向量夹角严格小于 $\pi$。

这样一定会覆盖所有满足要求的集合。取最大值即可。

#include<bits/stdc++.h>
#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=100000+10;
int n;
struct VEC {double x,y;}v[MAXN<<1],s;
double ans;
int getsq(VEC v) {
	if(v.x>=0&&v.y>=0) return 1;
	if(v.x<0&&v.y>=0) return 2;
	if(v.x<0&&v.y<0) return 3;
	return 4;	
}
bool operator <(VEC a,VEC b) {
	if(getsq(a)!=getsq(b)) return getsq(a)<getsq(b);
	return a.x*b.y-a.y*b.x>0;
}
VEC operator +(VEC A,VEC B) {return {A.x+B.x,A.y+B.y};}
VEC operator -(VEC A,VEC B) {return {A.x-B.x,A.y-B.y};}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) cin>>v[i].x>>v[i].y;
	VEC vc={0,0};
	ffor(i,1,n) vc=vc+v[i];
	sort(v+1,v+n+1);
	ffor(i,1,n) v[i+n]=v[i];
	int l=1,r=1; s=v[1],ans=max(ans,s.x*s.x+s.y*s.y);
	while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) {
		r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y);
	}	
	ffor(i,2,n) {
		l++,s=s-v[l-1];
		if(r<l) s=v[l],r=l;
		ans=max(ans,s.x*s.x+s.y*s.y);
		while(v[l].x*v[r+1].y-v[l].y*v[r+1].x>0) {
			r++,s=s+v[r],ans=max(ans,s.x*s.x+s.y*s.y);
		}
	}
	cout<<fixed<<setprecision(3)<<ans;
	return 0;
}