백준 10254번: 고속도로 (C++)

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

10254번: 고속도로

---

Solved By: Convex Hull, Rotating Calipers

 

최대 직경을 가지는 좌표를 구하는 문제입니다. Rotating Calipers를 가지고서 최대 직경을 갱신하며 최대 직경을 가지는 좌표 또한 갱신해주면서 코드를 작성하면 됩니다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define ll long long // 10^10이 넘는 경우 있음
using namespace std;

struct Point{
    ll x, y;
};

Point operator-(Point a, Point b){
    Point c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}

int T;
vector<Point> v;
vector<Point> vertex;
int n;

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

ll dist(Point a, Point b){
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

bool cmp(Point a, Point b){
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

bool cmp2(Point a, Point b){
    ll temp = ccw(v[0], a, b);
    if(temp == 0){
        return dist(v[0], a) < dist(v[0], b);
    }
    return temp > 0;
}

void convexHull(){
    stack<Point> s;
    s.push(v[0]); s.push(v[1]);
    int next = 2;
    while(next < v.size()){
        while(s.size() >= 2){
            Point first, second;
            second = s.top(); s.pop();
            first = s.top();
            
            if(ccw(first, second, v[next]) > 0){
                s.push(second); break;
            }
        }
        s.push(v[next]);
        next++;
    }
    
    vertex.resize(s.size());
    for(int i = vertex.size() - 1; i >= 0; i--){
        vertex[i] = s.top(); s.pop();
    }
    
    return;
}

pair<int, int> rotatingCalipers(){
    int pl = 0, pr = 0;
    int resl = 0, resr = 0;
    for(int i = 0; i < vertex.size(); i++){
        if(vertex[i].x < vertex[pl].x) pl = i;
        if(vertex[i].x > vertex[pr].x) pr = i;
    }
    
    Point po; po.x = 0; po.y = 0;
    
    ll distValue = dist(v[pl], v[pr]);
    resl = pl, resr = pr;
    
    for(int i = 0; i < vertex.size(); i++){
        if(ccw(po, vertex[(pl + 1) % vertex.size()] - vertex[pl]
        , vertex[pr] - vertex[(pr + 1) % vertex.size()]) > 0){
            pl = (pl + 1) % vertex.size();
        }
        else{
            pr = (pr + 1) % vertex.size();
        }
        
        if(distValue < dist(vertex[pl], vertex[pr])){
            distValue = dist(vertex[pl], vertex[pr]);
            resl = pl, resr = pr;
        }
    }
    
    return {resl, resr};
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    for(int t = 0; t < T; t++){
        v.clear(); vertex.clear();
        cin >> n;
        for(int i = 0; i < n; i++){
            ll a, b; cin >> a >> b;
            v.push_back({a, b});
        }
    
        sort(v.begin(), v.end(), cmp);
        sort(v.begin() + 1, v.end(), cmp2);
    
        convexHull();
        pair<int, int> result = rotatingCalipers();
        cout << vertex[result.first].x << ' ' << vertex[result.first].y << ' ';
        cout << vertex[result.second].x << ' ' << vertex[result.second].y << '\n';
    }
    return 0;
}