[BOJ] 9240 : 로버트 후드

#include<cstdio>
#include<algorithm>
#include<tuple>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct POINT{
    int x, y;
    bool operator <(POINT a)const {
        return x == a.x ? y < a.y : x < a.x;
    }
    POINT operator -(POINT a)const {
        return { x-a.x,y-a.y };
    }
};
int N;
ll sq(int x){
    return (ll)x*x;
}
ll dst(POINT A, POINT B) {
    return sq(A.x-B.x)+sq(A.y-B.y);
}
int ccw(POINT A, POINT B, POINT C){
    ll r = A.x*B.y + B.x*C.y + C.x*A.y;
    r -= A.y*B.x + B.y*C.x + C.y*A.x;
    if (r > 0) return 1;
    if (r < 0) return -1;
    return 0;
}

vector<POINT> GetConvexHull(vector<POINT> &p) {
    swap(p[0], *min_element(p.begin(), p.end()));
    sort(p.begin()+1, p.end(), [&](const POINT &A, const POINT &B){
        if(ccw(p[0], A, B) != 0){
            return ccw(p[0], A, B) < 0;
        }
        return dst(A, p[0]) < dst(B, p[0]);
    });
    vector<POINT> hull;
    hull.push_back(p[0]);
    for(int i = 1; i < N; i++){
        while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), p[i]) >= 0){
            hull.pop_back();
        }
        hull.push_back(p[i]);
    }
    return hull;
}

pii FarthestPair(vector<POINT> &hull) {
    pii ret;
    ll mx = -1;
    for (int i = 0, j = 0; i < hull.size(); i++) {
        while (j+1 < hull.size() && ccw({ 0,0 }, hull[i+1]-hull[i], hull[j+1]-hull[j]) <= 0) {
            if (mx < dst(hull[i], hull[j])) {
                mx = dst(hull[i], hull[j]);
                ret = { i,j };
            }
            j++;
        }
        if (mx < dst(hull[i], hull[j])) {
            mx = dst(hull[i], hull[j]);
            ret = { i,j };
        }
    }
    return ret;
}

int main(){
    scanf("%d", &N);
    vector<POINT> p(N);
    for (int i = 0; i < N; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }

    vector<POINT> hull = GetConvexHull(p);
    int a, b; tie(a, b) = FarthestPair(hull);
    printf("%.8lf", sqrt(dst(hull[a], hull[b])));

    return 0;
}