https://blog.csdn.net/tenkuo/article/details/154724690

G53 旋转卡壳【计算几何】

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
struct Point {
    double x, y;
    Point() {}
    Point(double a, double b) : x(a), y(b) {}
    void input() { scanf("%lf%lf", &x, &y); }
    friend bool operator<(Point a, Point b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
    friend Point operator-(Point a, Point b) { return {a.x - b.x, a.y - b.y}; }
    friend double det(Point a, Point b) { return a.x * b.y - a.y * b.x; }
    friend double dis(Point a, Point b) { Point p = a - b; return (p.x * p.x + p.y * p.y); }
};
Point P[N], sta[N]; int n, top;

void Andrew() {
    sort(P + 1, P + n + 1);
    top = 0;
    for (int i = 1; i <= n; i++) {
        while (top > 1 && det(sta[top] - sta[top - 1], P[i] - sta[top - 1]) <= 0) top--;
        sta[++top] = P[i];
    }
    int t = top;
    for (int i = n - 1; i >= 1; i--) {
        while (top > t && det(sta[top] - sta[top - 1], P[i] - sta[top - 1]) <= 0) top--;
        sta[++top] = P[i];
    }
    n = top - 1;
}

double rotating_calipers() { // 旋转卡壳
    double res = 0;
    for (int i = 1, j = 2; i <= n; i++) {
        while (det(sta[i + 1] - sta[i], sta[j] - sta[i]) < det(sta[i + 1] - sta[i], sta[j + 1] - sta[i])) j = j % n + 1;
        res = max(res, max(dis(sta[i], sta[j]), dis(sta[i + 1], sta[j])));
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) P[i].input();
    Andrew();
    printf("%.0lf\n", rotating_calipers());
    return 0;
}