假设确定了最终所得向量的方向，则应该选择所有在该方向上投影为正的向量。按极角序排序后这显然是一段连续区间。最终向量方向很难枚举，但对于某个向量，在其上投影为正的向量与其夹角范围是(-π/2,π/2)，所以只要枚举所有极角差不超过π的极长区间就可以了。这里的区间不是向量区间而是极角区间，相当于一条过原点的直线在旋转，所以双指针移动时每个向量区间都要更新答案。为了方便倍长向量数组，注意这样对于增加的那一半，极角需要加上2π。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 200010 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n; const double PI=3.14159266; ll ans; struct vector { int x,y;double angle; bool operator <(const vector&a) const { return angle<a.angle; } vector operator +(const vector&a) const { return (vector){x+a.x,y+a.y}; } vector operator -(const vector&a) const { return (vector){x-a.x,y-a.y}; } ll len(){return 1ll*x*x+1ll*y*y;} }a[N<<1]; int main() { #ifndef ONLINE_JUDGE freopen("bzoj5099.in","r",stdin); freopen("bzoj5099.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(); for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].angle=atan2(a[i].x,a[i].y); sort(a+1,a+n+1); for (int i=n+1;i<=n*2;i++) a[i]=a[i-n],a[i].angle+=2*PI; vector cur=(vector){0,0}; int x=0; for (int i=1;i<=n;i++) { while (x<n*2&&a[x+1].angle-a[i].angle<=PI) ans=max(ans,(cur=cur+a[++x]).len()); ans=max(ans,(cur=cur-a[i]).len()); } cout<<ans; return 0; }