#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct point
{
    int x;
    int y;
} pp[50010],p[50010];
int cross(point a,point b,point c)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
int dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int cmp1(point a,point b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
bool cmp2(point a,point b)
{
    if(cross(a,b,p[0])>0)
        return true;
    if(cross(a,b,p[0])<0)
        return false;
    if(cross(a,b,p[0])==0)
        dis(a,p[0])<dis(b,p[0])?true:false;
}
int main()
{
    int n;
    point s[50010];
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<n; i++)
            scanf("%d%d",&pp[i].x,&pp[i].y);
        sort(pp,pp+n,cmp1);
        int cnt=0;
        p[cnt].x=pp[0].x;
        p[cnt++].y=pp[0].y;
        for(int i=1; i<n; i++)
        {
            if(pp[i].x==pp[i-1].x&&pp[i].y==pp[i-1].y)
            {
                continue;
            }
            else
            {
                p[cnt].x=pp[i].x;
                p[cnt++].y=pp[i].y;
            }
        }
        n=cnt;
        if(n==1)
        {
            printf("0\n");
            continue;
        }
        if(n==2)
        {
            printf("%d\n",dis(p[0],p[1]));
            continue;
        }
        sort(p+1,p+n,cmp2);
        memset(s,0,sizeof(s));
        s[0]=p[0];
        s[1]=p[1];
        int top=1;
        for(int i=2; i<n; i++)
        {
            while(i>=1&&cross(p[i],s[top],s[top-1])>0)
                top--;
            s[++top]=p[i];
        }
        s[++top]=s[0];
        int j,k,ans=0;
        for(int i=0; i<top; i++)
        {
            j=(i+1)%top;
            k=(j+1)%top;
            while(abs(cross(s[j],s[(k+1)%top],s[i]))>abs(cross(s[j],s[k],s[i])))
                k=(k+1)%top;
            while(j!=i&&k!=i)
            {
                ans=max(ans,max(dis(s[i],s[k]),dis(s[i+1],s[k])));
                while(abs(cross(s[j],s[(k+1)%top],s[i]))>abs(cross(s[j],s[k],s[i])))
                    k=(k+1)%top;
                j=(j+1)%top;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

• Re:WA 请指教 (11) AK47biubiubiu 2017-01-07 20:46:44