백준 1310번: 달리기 코스 (C++)

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

1310번: 달리기 코스

---

Solved By: Convex Hull, Rotating Calipers

 

거리를 구하거나 CCW를 구하면서 int 범위를 넘는 경우가 생길 수 있으니 이 점을 유의하여 long long 타입으로 코드를 짜면 쉽게 풀리는 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;
}

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;
}

ll rotatingCalipers(){
    int pl = 0, pr = 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]);
    
    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();
        }
        
        distValue = max(distValue, dist(vertex[pl], vertex[pr]));
    }
    
    return distValue;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    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();
    cout << rotatingCalipers();
    
    return 0;
}