题面

飞花的传送门
Time Limit: 1000ms Memory limit: 65536K

题目描述
飞花壕最近手头比较宽裕，所以想买两个传送门来代步（夏天太热，实在是懒得走路）。平面上有N个传送门，飞花壕想要挑两个距离最远的传送门带回家（距离为欧几里得距离，即两点之间直线距离）。

请你帮他算一算他所挑选的最远的两个传送门有多远。

输入
多组输入。

对于每组输入，第一行输入一个整数N（2 <= N <= 50000），接下来从第2行到第N+1行，每行两个整数（Xi，Yi），代表第i个传送门的坐标（-1000000 <= Xi , Yi <= 1000000）。

数据为随机生成。

输出
输出一个整数，代表飞花壕要挑选的两个传送门的距离的平方。

示例输入
4
0 0
0 1
1 1
1 0

示例输出
2

提示

来源
GLSilence

所需基础

计算几何 - 凸包

解题思路

这题直接拿 POJ 2187 原题汉化了就搬过来当校赛题了，示例都一模一样，唯一的不同就是数据范围大了一些，需要用 long long，也是醉了。此题是标准的凸包裸题（对凸包的代码实现理解有困难的，可以参考我的这篇博客），和 POJ 2187 一样，求出凸包后枚举凸包上所有的点，两两构成线段，找出最大长度即可，不需要使用旋转卡壳。我这里用的是水平序的 Graham's Scan 算法，写起来会比极角序简单很多，而且不用纠结共线问题。

参考代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct point {
    long long x;
    long long y;
    point operator - (const point &p) const {
        point ret;
        ret.x = x - p.x;
        ret.y = y - p.y;
        return ret;
    }
} p[50000];

int n;

bool cmp(point a, point b) {    //水平序
    if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

long long Det(long long x1, long long y1, long long x2, long long y2) {
    return x1*y2 - x2*y1;
}

long long Cross(point a, point b, point p) {
    return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}

long long CalculateDistance(point a, point b) {
    point p = a - b;

    return p.x*p.x + p.y*p.y;
}

long long GrahamScan() {
    point res[50000];
    int top = 0;
    for(int i=0; i<n; ++i) {    //扫描右链
        while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    int tmp = top;
    for(int i=n-2; i>=0; --i) {    //扫描左链
        while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    long long ans = 0;
    for(int i=0; i<top; ++i) {    //枚举找最大长度
        for(int j=i+1; j<top; ++j) {
            ans = max(ans, CalculateDistance(res[i], res[j]));
        }
    }

    return ans;
}

int main(int argc, char const *argv[]) {
    while(~ scanf("%d", &n)) {
        for(int i=0; i<n; ++i) {
            scanf("%lld %lld", &p[i].x, &p[i].y);
        }
        sort(p, p+n, cmp);
        printf("%lld\n", GrahamScan());
    }
    
    return 0;
}