BOJ 2254 - 감옥 건설

www.acmicpc.net/problem/2254

2254번: 감옥 건설

 

이 문제는 볼록껍질(Convex Hull) 에 대해 알고 있어야 풀 수 있다.

 

- 참고 : blog.naver.com/kks227/220857597424

볼록 껍질(Convex Hull) (수정: 2019-08-15)

- CCW ? : degurii.tistory.com/47 

[알고리즘] CCW로 세 점의 방향성 판별하기

 

이 문제는 convex hull 의 갯수를 구하는 문제이다.

예제 입력 1을 예로 들면 그림이 다음과 같이 그려질 것이다.

빨간점은 감옥의 좌표 (-1, 0) 이고, 

나머지 파란점들은 담 기둥의 좌표이다

이때 convex hull 의 갯수는 2개 이다.

 

기존의 convex hull 을 구하는 알고리즘(Graham's scan)에서

감옥의 좌표가 해당 convex hull 에 포함되는지 파악하는 방법은 ccw 함수를 이용하는 것이다.

convex hull 을 구성하고 있는 좌표들과 감옥의 좌표의 ccw 함수의 값이 모두 같을때만 내부에 감옥이 있다고 볼수있다.

 

예를들어 convex hull 을 구성하는 5개의 점이 있고, 

감옥의 좌표가 하나 아래 처럼 있다면

ccw 함수 계산시 전부 반시계방향 값으로 나와야 한다

1

 

2

3

4

5

위의 5개 그림 모두 벡터 u 에서 벡터 v 로 의 방향이 반시계방향임을 알 수 있다.

정확한 ccw 의 값을 리턴해서 비교하기 보다는 방향성만 따지면 되므로

ccw 함수 계산시에 음수이면 -1, 양수이면 1, 0이면(평행) 0을 리턴하도록 해준다.

 

convex hull 내부에 감옥의 좌표가 있다는 것이 확인되면, 정답값을 하나 늘리고

처음에 입력받았던 모든 좌표들(감옥 좌표를 제외한 담의 좌표를 말함)중 지금 사용한 convex hull 의 좌표값을 제거해주는 작업이 필요하다.

(다음 convex hull 을 찾기위함)

convex hull 찾을때 사용했던 스택에서 사용된 좌표만 추려내는 것은 set 을 사용해서 해당좌표의 번호를 찾아내는 식으로 처리한다. (set 이 아닌 다른 컨테이너를 사용해도 처리가 될 것 같긴하다, 사용된 좌표만 지우면 되는것이니)

 

더이상 가능한 convex hull 이 없거나 남은 좌표 갯수가 2개 이하라면 프로그램을 종료한다.

 

 

- c++

#include <algorithm>
#include <iostream>
#include <stack>
#include <set>
#include <vector>
 
using namespace std;
 
struct Point {
    int x, y;
    int p, q;
    
    Point(){}
    Point(int x1, int y1, int p1 = 0, int q1 = 0): x(x1), y(y1), p(p1), q(q1){}
    
    bool operator<(const Point& O) {
        if (1LL * q * O.p != 1LL * p * O.q) return 1LL * q * O.p < 1LL * p * O.q;
        if (y != O.y) return y < O.y;
        return x < O.x;
    }
}; 
 
long long ccw(const Point& A, const Point& B, const Point& C) {
    long long temp = 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x);
    if (temp < 0) return -1;
    else if (temp == 0) return 0;
    else return 1;
}
 
vector<Point> vec;
int n, answer;
Point prison;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    cin >> prison.x >> prison.y;
    
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        vec.push_back(Point(x, y));
    }
    
    while(1) {
        // 아래는 convex hull 을 판별 하는 기능 
        // y 좌표 -> x 좌표 순으로 정렬 (가장 아래의 왼쪽에 있는 점이 0번점으로) 
        sort(vec.begin(), vec.end());
        
        for (int i = 1; i < vec.size(); ++i) {
            vec[i].p = vec[i].x - vec[0].x;
            vec[i].q = vec[i].y - vec[0].y;
        }
        
        // 0번 점을 제외한 나머지 점을 반시계방향 정렬 
        sort(++vec.begin(), vec.end());
        
        vector<Point> backup_vec = vec; // convex hull 을 한번 찾으면 다른 좌표에 대해서도 찾아야 하므로 백업본이 필요함. 
        stack<int> st, backup;
        st.push(0);
        st.push(1);
        
        int next = 2;
        
        while(next < vec.size()) {
            while(st.size() >= 2) {
                int first, second;
                second = st.top();
                st.pop();
                first = st.top();
                if (ccw(vec[first], vec[second], vec[next]) > 0) {
                    st.push(second);
                    break;
                }
            }
            st.push(next++);
        }
        
        // st 에 convex hull 에 해당하는 좌표들이 모두 담김
        // 아래는 px, py 가 convex hull 에 포함되는지 파악하는 기능 
        
        backup = st;
        int start = st.top();
        int first = st.top();
        st.pop();
        int second = st.top();
        st.pop();
        
        long long check = ccw(vec[first], vec[second], prison);
        bool inner = true;
        
        while(!st.empty()) {
            first = second; // 스택 순회하면서 다음 점으로 넘어가면서 ccw 파악 
            second = st.top();
            st.pop();
            
            if (check != ccw(vec[first], vec[second], prison)) {
                inner = false;
                break;
            }
        }
            
        // 시작점과 끝나는점도 ccw 를 해야함. 
        if (check != ccw(vec[second], vec[start], prison)) 
            inner = false;
        
        // 감옥이 convex hull 내부에 있으면 
        if (inner) {
            answer++;
            
            // 이전 convex hull 에 사용되었던 좌표를빼고 초기화함. 
            set<int> idx;
            for (int i = 0; i < vec.size(); ++i) idx.insert(i);
            
            while(!backup.empty()) {
                idx.erase(backup.top());
                backup.pop();
            } 
            
            // 입력 받았던 좌표중 사용된 좌표는 제거하고 나머지만 추가. 
            vec.clear();
            for (auto iter = idx.begin(); iter != idx.end(); ++iter) 
                vec.push_back(backup_vec[(*iter)]);
            
        } else {
            break;
        }
        
        if (vec.size() < 3) break; 
    }
    
    cout << answer;
    
    return 0;
}