[BOJ/Platinum 4] 백준 17403 가장 높고 넓은 성(C++)

문제 링크

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

17403번: 가장 높고 넓은 성

 

 

문제

당신은 어마어마한 크기의 토지를 소유한 부자다. 평지에는 n개의 표지판이 있다. 당신은 지금부터 이 곳에 민성이를 위한 성을 지을 것이다. 성은 여러 개의 층으로 구성된 구조물이다.

• 1층은 평지 위에 지어지고, 2층은 1층 위에, 3층은 2층 위에, ..., n층은 n-1층 위에 지어진다.
• 각 층의 경계는 다각형이며, 각 층의 경계의 꼭짓점에는 표지판이 위치하여야 한다. 다시 말하면, 표지판 위에만 각 층의 경계의 꼭짓점을 세울 수 있다.
• 한 표지판은 여러 층의 경계의 꼭짓점에 동시에 사용될 수 없다. 그러나 한 표지판이 다른 층의 꼭짓점이 아닌 경계에 위치할 수는 있다.
• 넓이가 0인 층은 허용되지 않는다.
• 쓸모가 없는 표지판들은 버려도 된다.

민성이는 숙소를 고를 때 전망을 최우선으로 고려하므로, 당신이 성을 지을 때 고려해야 할 우선순위는 다음과 같다.

1. 성의 높이를 가능한 한 제일 높게 지어야 한다.
2. 성의 모든 층의 넓이의 합이 가능한 한 제일 크게 지어야 한다.
3. 가능한 적은 수의 표지판을 사용하여야 한다.

당신은 성을 몇 층까지 지을 수 있으며, 그 때 각 층에 사용될 표지판들이 무슨 표지판인지 알아내야 한다.

입력

첫 번째 줄에 표지판의 개수 n이 주어진다. (1 ≤ n ≤ 103) 

두 번째 줄부터 n개의 줄에 걸쳐 각 표지판들의 위치를 의미하는 정수 x, y가 공백으로 구분되어 주어진다. (-104 ≤ x, y ≤ 104) 이는 (x, y)에 표지판이 위치함을 의미한다.

모든 표지판은 서로 다른 위치에 세워져 있다.

출력

첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다.

예제 입력 1

9
0 0
-1 3
-1 -2
-5 -5
2 -2
2 2
3 1
3 -5
1 -1

예제 출력 1

2 1 2 1 2 1 1 1 0

파란색 점들이 1층에 사용된 표지판들, 주황색 점들이 2층에 사용된 표지판들, 그리고 보라색 점이 버려진 표지판을 의미한다.

예제 입력 2

12
0 0
1 0
2 0
3 0
4 0
3 1
2 2
1 3
0 4
0 3
0 2
0 1

예제 출력 2

1 2 3 2 1 2 3 2 1 2 3 2

알고리즘 분류

• 그레이엄 스캔
• 자료 구조

풀이

성의 모든 층의 넓이가 무조건 커야 하고 최소한의 표지판만 사용해야하므로, 가장자리에 있는 표지판만을 둘러싸도록 성을 짓는다.

그레이엄 스캔을 통해 가장자리에 있는 표지판만을 찾아 성을 짓고, 안쪽에 있는 표지판들을 대상으로 또 그레이엄 스캔을 통해 성을 짓는다.

이것을 더 이상 성을 지을 수 없을 때까지 반복한다.

성을 지을 수 있으려면, 3개 이상의 표지판이 좌회전(또는 우회전)을 이루어야 하며, 표지판이 3개 이상이어도 같은 직선 상에 존재한다면 성의 넓이가 0이 되기 때문에 허용되지 않는다.

이렇게 모든 조건을 만족하면서 성을 짓고 나서 표지판이 몇 층의 성을 지을 때 사용되었는지 기록하기 위해 해싱을 사용한다.

N개의 표지판을 입력받을 때 map을 활용하여 해싱을 한 후, 표지판이 몇 층의 성을 지을 때 사용되었는지 각 표지판의 인덱스를 활용하여 기록한다.

그런데 구조체를 key로 지정하려면, 구조체 내부에서 연산자를 오버라이딩해야한다. X좌표를 비교하고, X좌표와 같다면 Y좌표와 비교하도록 연산자를 오버라이딩해주자.

마지막은 각 표지판이 몇 층의 성을 지을 때 사용되었는지를 공백을 통해 구분하여 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <algorithm>
#define MAX 1001
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POINT {
    LL X, Y;

    bool operator<(const POINT &A) const {
        if (X != A.X) {
            return (X < A.X);
        }
        return (Y < A.Y);
    }
};

LL N, X, Y, MinX, MinY, First;
vector<POINT> Point;
vector<POINT> CV;
map<POINT, int> UM;
int Castle = 1;
bool Flag = true;
int Answer[MAX];

void init() {
    MinX = INF;
    MinY = INF;
    CV.clear();
}

LL distance(POINT A, POINT B) {
    return (A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y);
}

LL CCW(POINT A, POINT B, POINT C) {
    LL OP = ((A.X * B.Y) + (B.X * C.Y) + (C.X * A.Y));
    OP -= ((A.Y * B.X) + (B.Y * C.X) + (C.Y * A.X));
    return OP;
}

bool Comp(POINT A, POINT B) {
    LL NowCCW = CCW(Point[0], A, B);
    if (NowCCW != 0) {
        return (NowCCW > 0);
    }
    if (A.X != B.X) {
        return (A.X < B.X);
    }
    return (A.Y < B.Y);
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        POINT Tmp;
        Tmp.X = X;
        Tmp.Y = Y;
        Point.push_back(Tmp);
        UM[Tmp] = i;
    }
}

void graham_Scan() {
    if (Point.size() <= 2) {
        Flag = false;
        return;
    }
    for (int i = 0; i < Point.size(); i++) {
        if ((MinX > Point[i].X) || ((MinX == Point[i].X) && (MinY > Point[i].Y))) {
            MinX = Point[i].X;
            MinY = Point[i].Y;
            First = i;
        }
    }
    swap(Point[0], Point[First]);
    sort(Point.begin() + 1, Point.end(), Comp);
    for (int i = 0; i < Point.size(); i++) {
        while ((CV.size() >= 2) && (CCW(Point[i], CV[CV.size() - 2], CV[CV.size() - 1]) <= 0)) {
            CV.pop_back();
        };
        CV.push_back(Point[i]);
    }
    if (CV.size() <= 2) {
        Flag = false;
        return;
    }
    for (int i = 0; i < CV.size(); i++) {
        Answer[UM[CV[i]]] = Castle;
        for (int j = 0; j < Point.size(); j++) {
            if ((Point[j].X == CV[i].X) && (Point[j].Y == CV[i].Y)) {
                Point.erase(Point.begin() + j);
                break;
            }
        }
    }
}

void settings() {
    while (1) {
        init();
        graham_Scan();
        if (!Flag) {
            break;
        }
        Castle++;
    };
}

void find_Answer() {
    for (int i = 0; i < N; i++) {
        cout << Answer[i] << " ";
    }
    cout << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}