백준 10903번: Wall construction (C++)

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

10903번: Wall construction

---

Solved By: Geometry, Convex Hull

 

이번 문제는 Convex Hull과 Geometry의 기본적인 지식을 가지고서 풀 수 있었습니다.

 

"홍준이는 미니멀리즘을 추구하기 위해 가장 최소한의 유리 벽을 사용하여 외벽을 만들고자 한다."

>> 다음 부분에서 Convex Hull을 사용하여 최소한의 기둥을 사용해야 함을 알 수 있습니다.

 

하단 코드를 보면 전역으로 선언된 스택에 해당 좌표들이 담겨있으므로 스택에서 꺼내서 거리를 구할 수 있습니다.

>> getLine() function 참고

 

그리고, 기하학에 관한 지식이 필요한데 최소한의 유리 벽을 고르게 되고, 사용되는 유리 벽의 길이를 구할 때

원으로 덮는 부분은 어떻게 구현해야 할지 고민해야 합니다.

 

예를 들어, 삼각형이라고 할 때 각각의 내각들을 a, b, c라고 하겠습니다.

각이 a인 지점에서 유리가 덮는 부분의 각은 360(원의 전체) - (a + 90 + 90)도입니다.

>> 90도는 한 변에서부터 직선으로 그었을 때, 원주를 가로지르는 부분에서 나옵니다.

>> 두 개가 나오므로 90도를 2번 빼줍니다.

 

나머지 b와 c에도 적용하면

180 * 3 - (a + b + c)가 되고, a + b + c는 삼각형의 내각의 합이므로

180 * n - (n - 2) * 180(n각형의 내각의 합 공식)으로 정리하여

>> 어떤 n각형이든 360가 나오게 됩니다.

>> 이는 반지름 값을 안 상태에서 원주를 더해주면 끝나게 됩니다.

 

+ 추가적으로 알아야 할 사항

 

이번 문제를 통해 수학 상수들을 사용할 수 있게 되었습니다. (원주율 근삿값 상수)

// 원주율 pi 사용법
#define _USE_MATH_DEFINES
#include <cmath>
// M_PI == pi

그리고 long long 타입의 sqrt()와 pow()를 사용해보았습니다.

 

[AC 코드]

// 원주율 pi 사용법
#define _USE_MATH_DEFINES
#include <cmath>
// M_PI == pi
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define lld long double
#define ll long long
using namespace std;

typedef struct{
    ll x, y;
} Point;

int n, r;
vector<Point> v;
stack<int> s;

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

lld dist(Point a, Point b){
    // long double sqrt == sqrtl
    // long double pow == powl >> c++ 어느 헤더? >> cmath
    return (lld)sqrtl(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;
    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(){
    s.push(0); s.push(1);
    
    int next = 2;
    while(next < n){
        while(s.size() >= 2){
            int first, second;
            second = s.top(); s.pop();
            first = s.top();
            
            if(ccw(v[first], v[second], v[next]) > 0){
                s.push(second); break;
            }
        }
        
        s.push(next++);
    }
}

lld getLine(){
    int temp = s.top();
    lld ret = 0;
    
    while(s.size() >= 2){
        int first, second;
        second = s.top(); s.pop();
        first = s.top();
        
        ret += dist(v[first], v[second]);
    }
    
    ret += dist(v[temp], v[s.top()]);
    return ret;
}

int main(){
    cin >> n >> r;
    
    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();
    lld result = getLine();
    
    cout << fixed;
    cout.precision(12);
    //cout << result << '\n';
    cout << (2 * r * M_PI) + result;
    
    return 0;
}