백준 10254 고속도로 C++

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

좌표 평면위의 점의 최장 거리를 이루는 두 점은 하나의 볼록 껍질 위에 존재한다는 것을 이용해서 푼다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct P{
    ll x, y;
    P operator- (P a) { 
        return { x - a.x, y - a.y };
    }
}b[200001];
vector<P> v;
ll ccw(P p1, P p2) {
    ll ret = p1.x*p2.y - p2.x*p1.y;
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
ll ccw(P c, P a, P b) {
    return ccw(a - c, b - c);
}
ll sqdis(P p1, P p2) {
    return (p1.x - p2.x) *(p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmp(P p1, P p2) {
    ll ret = ccw(b[0], p1, p2);
    if (ret > 0) return true;
    else if (ret < 0) return false;
    else {
        if (sqdis(b[0], p1) < sqdis(b[0], p2)) return true;
        else return false;
    }
}
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int Min = 111111111, idx = 0; //y값 최소 다음 x값 최소
        for (int i = 0; i < n; i++) {
            cin >> b[i].x >> b[i].y;
            if (b[i].y < Min) {
                Min = b[i].y;
                idx = i;
            }
            else if (b[i].y == Min) {
                if (b[i].x < b[idx].x) idx = i;
            }
          }
        swap(b[0], b[idx]);
        sort(b + 1, b + n, cmp);
        
        //graham scan
        for (int i = 0; i < n; i++) {
            while (v.size() >= 2 && ccw(v[v.size() - 2], v[v.size() - 1], b[i]) <= 0) {
                v.pop_back(); 
            }
            v.push_back(b[i]);
        }
        v.push_back(b[0]); //마지막에 첫점 연결
 
        ll ans = -1;
        int j = 1, st, en;
        for (int i = 0; i < v.size()-1; i++) {
            while (i != j && ccw(v[i + 1] - v[i], v[j + 1] - v[j]) > 0) {
                j++;
                if (j >= v.size() - 1) j = 0;
            }
            ll dist = sqdis(v[i], v[j]); //ccw가 양수가 아니게 되는 순간마다 거리 측정
            if (ans < dist) {
                st = i;
                en = j;
                ans = dist;
            }
        }
        printf("%lld %lld %lld %lld\n", v[st].x, v[st].y, v[en].x, v[en].y);
        v.clear();
    }
    return 0;
}