为什么这样就可以过啊qwq感觉很玄学
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct point
{
int x,y;
}a[400005];
int calctype(point x)
{
if(x.y>0)return 1;
if(x.y<0)return 3;
if(x.x>=0)return 0;
return 2;
}
ll cross(point u,point v)
{
return 1ll*u.x*v.y-1ll*v.x*u.y;
}
ll dot(point u,point v)
{
return 1ll*u.x*v.x+1ll*u.y*v.y;
}
bool cmp(point x,point y)
{
return calctype(x)<calctype(y)||calctype(x)==calctype(y)&&cross(x,y)>0;
}
ll ans;
void updans(int x,int y)
{
ans=max(ans,1ll*x*x+1ll*y*y);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
if(!a[i].x&&!a[i].y)i--,n--;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)a[i+n]=a[i];
int l=1,r=1,sumx=0,sumy=0;
while(l<=n)
{
while(r<=l||r<n+l&&cross(a[l],a[r])>0)
{
sumx+=a[r].x;
sumy+=a[r].y;
r++;
updans(sumx,sumy);
}
sumx-=a[l].x;
sumy-=a[l].y;
updans(sumx,sumy);
l++;
}
l=1,r=1,sumx=0,sumy=0;
while(l<=n)
{
while(r<l||r<n+l&&cross(a[l],a[r])>=0)
{
sumx+=a[r].x;
sumy+=a[r].y;
r++;
updans(sumx,sumy);
}
sumx-=a[l].x;
sumy-=a[l].y;
updans(sumx,sumy);
l++;
}
printf("%lld\n",ans);
return 0;
}
/*
5
2 -2
-2 -2
0 2
3 1
0 100
4Y
1 -1
1 -1
-2 1
2 1
*/