挺好的题。。
我只想到了按照极角排序之后最优的选择方案一定是连续的一段（注意这是一个圆所以要拓展两倍）。
证明：如果我们知道了最终向量的方向，那么显然的一点是我们只会选择那些极角差小于$pi /2$的向量（这个可以用向量的加减法来证长度的变化）。
然后就是优化了。我们枚举所有的$[l,r]$里面包括很多无法达成的情况，即不存在一个最终向量使得选取的区间恰好是$[l,r]$。正解的方法是维护一个pos代表右端点为i时，满足$atan2(y[r],x[r])-atan2(y[l],x[l])<=pi$的最左端点。然后在$++pos$的过程中用$[pos+1,i-1]$来更新答案。这样是$O(n)$的。
证明：我们只需要证明对于一个左端点$l$，满足$atan2(y[r+1],x[r+1])-atan2(y[l-1],x[l-1])<pi$时，$[l,r]$不可能满足条件即可。这个很显然了。。一半大于$pi /2$那么另一半一定小于$pi /2$的。
#include <bits/stdc++.h> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define for1(a,b,i) for(int i=a;i<=b;++i) #define FOR2(a,b,i) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; inline int read() { int f=1,sum=0; char x=getchar(); for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1; for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0'; return f*sum; } #define M 400005 int n; ll ans; int ax[M],ay[M]; const double pi=acos(-1); struct node { int x,y; double k; inline void in() { x=read(),y=read(),k=atan2(y,x); } inline bool operator <(const node &a) const { return k<a.k; } }a[M]; inline void check(int l,int r) { ll t=1ll*(ax[r]-ax[l-1])*(ax[r]-ax[l-1])+1ll*(ay[r]-ay[l-1])*(ay[r]-ay[l-1]); ans=max(ans,t); } int main() { //freopen("a.in","r",stdin); n=read(); for1(1,n,i) a[i].in(); sort(a+1,a+n+1); for1(1,n,i) a[n+i]=a[i],a[n+i].k=a[i].k+2*pi; for1(1,2*n,i) ax[i]=ax[i-1]+a[i].x,ay[i]=ay[i-1]+a[i].y; int h=1; for1(1,2*n,i) { while (h<i&&a[h].k+pi<a[i].k) ++h,check(h,i-1); check(h,i); } cout<<ans<<endl; }