백준 17403번: 가장 높고 넓은 성 (C++)

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

17403번: 가장 높고 넓은 성

---

Solved By: Convex Hull (Monotone Chain)

 

Convex Hull의 기법 문제인 줄 알았던 문제였습니다. 그 덕에 Monotone Chain기법을 공부할 수 있었습니다. 공부를 하고 나서 알았지만 이건 기법의 문제가 아니었습니다.

(https://draw-code-boy.tistory.com/269)

 

조건만 잘 따져주면 풀리는 문제였습니다. 그리고 index까지 신경 써줘야 하다 보니 구현이 조금 까다롭기도 합니다.

1. 조건

2. 구현력 (인덱스를 어떻게 구현할 것인가)

 

사실상 생각해보면 구조체를 선언할 때, index까지 선언해주면 끝나는 문제입니다.

다만, 이 문제는 조건이 살짝 까다로웠습니다.

 

블록 껍질은 만들고 나서 점이 2개가 남았을 때, 종료를 시키는 건 충분히 알 수 있었습니다.

하지만, 다른 조건은 반례를 보고 나서야 알 수 있었습니다.

input
3 1 1 2 2 3 3 
answer
0 0 0

해당 좌표를 토대로 2차원 평면에 그려보면 일직선으로 연결되어있는 것을 알 수 있습니다. 해당 케이스를 통해 볼록 껍질을 만들었을 때, 볼록 껍질을 구성하는 좌표가 2개 이하라면 이건 성립이 될 수 있음을 알려주면 됩니다.

 

>> 조건 정리

1. convexHull을 만드려는데 점이 2개 남았을 때

2. convexHull을 만들었는데 구성하는 점이 2개 이하일 때

 

[AC 코드]

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#define MAX 1001
#define ll long long
using namespace std;

struct p{
    ll x, y;
    int idx; // 몇 번째 점인지를 알아야 한다.
    
    bool operator <(const p &point){
        return x < point.x || (x == point.x && y < point.y);
    }
};

int n;
int tower[MAX];
bool visited[MAX];
vector<p> v;
p tp;

ll ccw(p a, p b, p c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

ll dist(p a, p b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

vector<p> convexHull(vector<p> points){
    // monotone chain
    
    sort(points.begin(), points.end());
    
    vector<p> uh;
    int un = 0;
    for(int i = 0; i < points.size(); i++){
        while(un >= 2 && ccw(uh[un - 2], uh[un - 1], points[i]) >= 0){
            uh.pop_back(); --un;
        }
        uh.push_back(points[i]); ++un;
    }
    uh.pop_back();
    
    reverse(points.begin(), points.end());
    
    vector<p> dh;
    int dn = 0;
    for(int i = 0; i < points.size(); i++){
        while(dn >= 2 && ccw(dh[dn - 2], dh[dn - 1], points[i]) >= 0){
            dh.pop_back(); --dn;
        }
        dh.push_back(points[i]); ++dn;
    }
    dh.pop_back();
    
    vector<p> ret;
    for(int i = 0; i < uh.size(); i++) ret.push_back(uh[i]);
    for(int i = 0; i < dh.size(); i++) ret.push_back(dh[i]);
    return ret;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        ll a, b; cin >> a >> b;
        v.push_back({a, b, i});
    }
    
    int floorValue = 1;
    int pointCnt = 0;
    // convexHull을 만드려는데 점이 2개 남았을 때
    while(pointCnt + 2 < n){
        vector<p> temp;
        for(int i = 0; i < n; i++){
            if(!visited[i]){
                temp.push_back({v[i].x, v[i].y, i});
            }
        }
        
        vector<p> polygon = convexHull(temp);
        
        if(polygon.size() <= 2){
            // convexHull이 만들어졌는데 그 점이 2개 이하일 때
            for(int i = 0; i < polygon.size(); i++){
                visited[polygon[i].idx] = 1;
                tower[polygon[i].idx] = 0;
            }
        }
        else{
            for(int i = 0; i < polygon.size(); i++){
                visited[polygon[i].idx] = 1;
                tower[polygon[i].idx] = floorValue;
            }
            ++floorValue;
        }
        pointCnt += polygon.size();
    }
    
    for(int i = 0; i < n; i++) cout << tower[i] << ' ';
    return 0;
}