백준 2049번: 가장 먼 두 점 (C++)

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

2049번: 가장 먼 두 점

---

Solved By: Convex Hull, Rotating Calipers

 

단순한 Rotating Calipers 문제였습니다. Rotating Calipers 문제를 처음 접할 때, 좋은 문제일 거 같습니다.

거리의 제곱을 구한다는 점만 인지하고 있으면 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#define ll long long
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; // convexHull
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 powl(a.x - b.x, 2) + powl(a.y - b.y, 2);
}

bool cmp(Point a, Point b){
    if(a.y != b.y) return a.y < b.y;
    else 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 = s.size() - 1; i >= 0; i--){
        vertex[i] = s.top(); s.pop();
    }
}

int main(){
    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();
    
    // rotating calipers
    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;
    }
    
    ll distValue = dist(vertex[pl], vertex[pr]);
    Point po; po.x = 0; po.y = 0;
    
    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]));
    }
    
    cout << distValue;
    return 0;
}