MyPojId == zhaozhouyang

    以前这道题目暴力枚举是可以过的，但是数据貌似增强了，旋转卡壳算法即可。

    排序只需按x最小y最小即可，然后分左链和右链找凸包即可。

#include<iostream>
#include<algorithm>
using namespace std;
int ans[50004];
struct Node
{
    int x;
    int y;
}v[50004];
bool cmp(Node a, Node b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y  < b.y;
}
int multi(Node a, Node b, Node c, Node d)
{
    b.x -= a.x;
    b.y -= a.y;
    d.x -= c.x;
    d.y -= c.y;
    return b.x * d.y - d.x * b.y;
}
bool notleft(Node a, Node b, Node c)
{
    return multi(a, b, b, c) <= 0;
}
int dist(Node a, Node b)
{
    return (a.x - b.x) * (a.x - b.x) (a.y - b.y) * (a.y - b.y);
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i )
        scanf("%d %d", &v[i].x, &v[i].y);
    sort(v, v n, cmp);
    int tail = 0;
    ans[tail ] = 0; ans[tail ] = 1;
    int temp = 2;
    while(temp < n)
    {
        if (tail > 1 && notleft(v[ans[tail - 2]], v[ans[tail - 1]], v[temp]))
            tail--;
        ans[tail ] = temp ;
    }
    ans[tail ] = n - 2;
    temp = n - 3;
    while(temp >= 0)
    {
        if (tail > 1 && notleft(v[ans[tail - 2]], v[ans[tail - 1]], v[temp]))
            tail--;
        ans[tail ] = temp--;
    }
    int dis = -1;
    for(int i = 0; i < tail; i )
        for(int j = i 1; j < tail; j )
        {
            int d = dist(v[ans[i]], v[ans[j]]);
            if (d > dis)
                dis = d;
        }
    printf("%d\n", dis);

    return 0;
}