9240번: Robert Hood

https://www.acmicpc.net/problem/9240

$O(n\lg n)$

#include<cstdio>
#include<algorithm>
#define x first
#define y second
#define dis(a,b) hypot(a.x-b.x,a.y-b.y)
using namespace std;
const int MXN = 1e5;
int t, n;
typedef struct pair<int, int> point;
point p[MXN], ch[MXN];
int ccw(point a, point b, point c) {
    return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &p[i].x, &p[i].y);
    swap(p[0], *min_element(p, p + n));
    sort(p + 1, p + n, [](point l, point r) {
        int c = ccw(p[0], l, r);
        return c > 0 || !c && l < r;
    });
    int sz = 0;
    for (int i = 0; i < n; i++) {
        while (sz > 1 && ccw(ch[sz - 2], ch[sz - 1], p[i]) <= 0) sz--;
        ch[sz++] = p[i];
    }
    double maxi = 0;
    for (int i = 0, j = 1; i < sz; i++) {
        while (ccw(ch[i], ch[(i + 1) % sz], { ch[i].x + ch[(j + 1) % sz].x - ch[j].x, ch[i].y + ch[(j + 1) % sz].y - ch[j].y }) > 0) j = (j + 1) % sz;
        if (maxi < dis(ch[i], ch[j])) maxi = dis(ch[i], ch[j]);
    }
    printf("%lf", maxi);
    return 0;
}