旋转卡壳解决最远点对。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 5e4 + 5;
const double EPS = 1e-6;
const int INF = 0x7fffffff;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x;
        double yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }
    void input()
    {
        scanf("%lf%lf", &x, &y);
    }

    bool operator <(Point &rhs)
    {
        if(fabs(y - rhs.y) <= EPS) return x < rhs.x;
        return y < rhs.y;
    }
    double x, y;
    double v, l;
    int id;
};
Point operator -(Point lhs, Point rhs){return Point(rhs.x - lhs.x, rhs.y - lhs.y);}
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}

Point src;

bool cmp(Point &a, Point &b)
{
    double temp = (a - src) ^ (b - src);
    if(fabs(temp) <= EPS) return a.getDis(src) < b.getDis(src);
    return temp > 0;
}

int stack[MAXN];
void getConvex(vector<Point> &a, vector<Point> &out)
{
    out.clear();
    sort(a.begin(), a.end(), cmp);

    stack[0] = 0;
    stack[1] = 1;
    int top = 1;
    for(int i = 2; i < (int)a.size(); ++i)
    {
        while(top >= 1 && ((a[i] - a[stack[top - 1]]) ^ (a[stack[top]] - a[stack[top - 1]])) >= 0)
        {
            --top;
        }
        stack[++top] = i;
    }
    for(int i = 0; i <= top; ++i) out.push_back(a[stack[i]]);
}

double getDiameterOfConvex(vector<Point> &p, int &fst, int &scnd)
{
    int n = p.size();
    double maxd = 0.0;
    if(n == 1)
    {
        fst = scnd = 0;
        return maxd;
    }
    #define next(i) ((i + 1) % n)
    for(int i = 0, j = 1; i < n; ++i)
    {
        double temp1 = (p[next(i)] - p[i]) ^ (p[j] - p[i]);
        double temp2 = (p[next(i)] - p[i]) ^ (p[next(j)] - p[i]);
        while(temp1 - temp2 < 0)
        {
            j = next(j);
            temp1 = (p[next(i)] - p[i]) ^ (p[j] - p[i]);
            temp2 = (p[next(i)] - p[i]) ^ (p[next(j)] - p[i]);
        }
        double dis = p[i].getDis(p[j]);
        if(dis > maxd)
        {
            maxd = dis;
            fst = i;
            scnd = j;
        }
        dis = p[next(i)].getDis(p[next(j)]);
        if(dis > maxd)
        {
            maxd = dis;
            fst = i;
            scnd = j;
        }
    }
    return maxd;
}

int n;
vector<Point> point;
vector<Point> convex;

int main()
{
    scanf("%d", &n);
    Point temp;
    for(int i = 1; i <= n; ++i)
    {
        temp.input();
        point.push_back(temp);
        if(i == 1)
        {
            src = temp;
        }
        else if(temp < src)
        {
            src = temp;
        }
    }

    getConvex(point, convex);
    int a, b;
    double ans = getDiameterOfConvex(convex, a, b);
    printf("%.0lf\n", ans * ans);
}