백준 7420번: 맹독 방벽 (C++)

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

7420번: 맹독 방벽

---

Solved By: Convex Hull (Graham Scan)

 

문제에서 주어진 그림 중 점선으로 이어진 선들이 구해야 하는 벽인 줄 알고, '저걸 어떻게 convex hull로 구하나..' 생각하다가 점선이 구해야하는 벽임을 깨달았습니다.

그래서, Graham Scan을 이용한 Convex Hull로 점들을 구해주고, 거리를 구해주며 저번에 사용했던 원 벽의 길이를 구하는 테크닉을 사용하여 거리를 구해줍니다. (https://draw-code-boy.tistory.com/266)

거리는 실수형이고, 결괏값은 정수형으로 반올림하여 출력하라 했으므로 floor(N + 0.5) 테크닉을 이용하여 반올림한 정수형 결과를 도출해줍니다.

 

#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
#define ld long double
using namespace std;

struct Point{
    ll x, y;
};

vector<Point> v;
int n, l;

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

ld dist(Point a, Point b){
    return (ld)sqrtl(powl(a.x - b.x, 2) + powl(a.y - b.y, 2));
}

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

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

ld grahamScan(){
    vector<int> s;
    
    s.push_back(0); s.push_back(1);
    int next = 2;
    while(next < n){
        while(s.size() >= 2){
            int first, second;
            second = s.back(); s.pop_back();
            first = s.back();
            
            if(ccw(v[first], v[second], v[next]) > 0){
                s.push_back(second); break;
            }
        }
        s.push_back(next++);
    }
    
    ld ret = 0;
    for(int i = 0; i < s.size(); i++){
        int j = (i + 1) % s.size();
        //cout << '{' << v[s[i]].x << ' ' << v[s[i]].y << '}' << '\n';
        //cout << '{' << v[s[j]].x << ' ' << v[s[j]].y << '}' << '\n';
        //cout << '\n';
        ret += dist(v[s[i]], v[s[j]]);
    }
    
    return ret;
}

int main(){
    cin >> n >> l;
    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);
    
    ld polygonDist = grahamScan();
    //cout << polygonDist << '\n';
    ld result = polygonDist + (ld)(M_PI * 2 * (ld)l);
    
    int result2 = (int)floor(result + 0.5);
    cout << result2;
    return 0;
}