关于本题整数做法
查看原帖
关于本题整数做法
353976
Yuzu_Soft楼主2024/12/25 11:39

为什么这样就可以过啊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

*/
2024/12/25 11:39
加载中...