백준 9240번: 로버트 후드 (C++)

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

9240번: 로버트 후드

---

Solved By: Convex Hull, Rotating Calipers

 

처음으로 사용해본 Rotating Calipers 문제였습니다. Point 간의 계산을 간편화 하기 위해 Point operator를 따로 선언하였습니다.

long double result = sqrt(distValue);

그리고, distValue가 long long type의 데이터인데 sqrt를 시키면 이때까지 long long 형태로 남아서 소수 자리가 없을 줄 알았으나 이번에 시도해본 코드로 long double형(소수)이 담길 수 있다는 것을 알았습니다.

 

+ 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]));
    }
    
    long double result = sqrt(distValue);
    cout.precision(8);
    cout << fixed;
    
    cout << result;
    return 0;
}