백준 6194번: Buliding the Moat (C++)

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

6194번: Building the Moat

---

Solved By: Convex Hull

 

Graham Scan 기법을 이용한 Convex Hull을 활용하여 모든 watering holes를 보호해야 합니다.

구한 점들을 가지고서 점들 사이의 거리를 구하면 됩니다.

이때 저번에 어디선가 본 테크닉을 이용하였습니다.

 

j가 끝점이 되는데 끝점에서 시작점까지의 거리를 복잡하게 구현하지 않고 나머지 연산을 이용하여 다음과 같이 편하게 구할 수 있습니다.

for(int i = 0; i < s.size(); i++){
    int j = (1 + i) % s.size();
    result += dist(p[s[i]], p[s[j]]);
}

그리고, 이번에 이 테크닉이 사용 가능했던 이유는 점들의 데이터를 담은 data structure가 stack이 아닌 vector로 풀어보았기 때문입니다.

 

+ 이번에는 typedef을 사용하지 않고, [struct 타입명]의 방식으로 struct를 선언하였습니다. typedef가 옛 방식이라는 것을 보고, 다른 방법으로 시도해보았습니다.

 

결론적으로 이번 문제의 핵심은 풀었던 방식입니다.

• stack 대신 vector 사용
• 끝점과 시작점 사이의 거리 간단하게 구현하기

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define ll long long
#define ld long double
#define pu push_back
#define po pop_back
using namespace std;

struct Point{
    ll x, y;
};
int n;
vector<Point> p;

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.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

bool cmp2(Point a, Point b){
    ll ccwv = ccw(p[0], a, b);
    if(ccwv == 0) return dist(p[0], a) < dist(p[0], b);
    return ccwv > 0;
}

ld convexHull(){
    vector<int> s;
    s.pu(0); s.pu(1);
    int next = 2;
    
    while(next < n){
        while(s.size() >= 2){
            int first, second;
            second = s[s.size() - 1]; s.po();
            first = s[s.size() - 1];
            
            if(ccw(p[first], p[second], p[next]) > 0){
                s.pu(second); break;
            }
        }
        s.pu(next++);
    }
    
    ld result = 0;
    for(int i = 0; i < s.size(); i++){
        int j = (1 + i) % s.size();
        result += dist(p[s[i]], p[s[j]]);
    }
    
    return result;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        ll a, b; cin >> a >> b;
        p.pu({a, b});
    }
    
    sort(p.begin(), p.end(), cmp);
    sort(p.begin() + 1, p.end(), cmp2);
    
    cout << fixed;
    cout.precision(2);
    cout << convexHull();
    return 0;
}