[BOJ/Platinum 5] 백준 4181 Convex Hull(C++)

문제 링크

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

4181번: Convex Hull

 

문제

때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소양이 되었다.

이 작업은 크게 두 단계의 과정으로 이루어진다. 첫 번째 단계는 볼록 껍질을 이루는 점들을 찾아내는 것이고, 두 번째 단계는 이 점들을 반시계 방향으로 순서를 매기는 것이다. 첫 번째 단계는 이미 완료되었다고 할 때, 두 번째 단계를 수행하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 점의 개수 n이 주어진다. (3 <= n <= 100,000)

두 번째 줄부터 n개의 줄에 걸쳐 각 점에 대한 정보 x, y, c가 주어진다. x, y는 정수이며 절댓값이 1,000,000,000을 넘지 않고, c는 Y 또는 N인 문자이다. Y는 이 점이 볼록 껍질에 속해있음을, N이면 아님을 의미한다.

중복되는 점은 없으며, 모든 점이 한 직선 위에 있는 경우도 없다.

출력

첫 번째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

이어서 한 줄에 하나씩 그 점들의 좌표를 x y 형태로 출력하는데, 이 점들은 반시계 방향으로 순서를 이루어야 한다. 첫 번째 좌표는 x좌표가 가장 작은 점이어야 하며, 만약 그런 좌표가 여러 개라면 그 중에서 y좌표가 가장 작은 점을 선택한다.

예제 입력 1

5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y

예제 출력 1

4
-1 -1
1 -1
1 1
-1 1

알고리즘 분류

• 그레이엄 스캔

풀이

그레이엄 스캔을 통해 볼록 껍질의 외곽을 구성하는 점을 찾아 반시계 방향으로 정렬한다.

우선 볼록 껍질에 포함되어 있는 점들, 그러니까 Y인 점들만 빼고 N인 점들은 제외시키고 정렬을 시작한다.

처음에는 X좌표가 가장 적고, X좌표가 최소인 점이 여러 개가 존재한다면 Y좌표가 가장 낮은 점을 찾아 정렬할 때 가장 먼저 오게 한다.

그리고 나머지 점을 반시계 방향, 즉  → ↑ ← ↓ 순으로 정렬한다.

반시계 방향임을 알 수 있는 방법은 현재 점과 그 전, 그 전 전 점이 좌회전을 이룰 때이다.

좌회전임을 알 수 있는 방법은 세 개의 점의 CCW가 0보다 큰 지 확인하는 것이다.

마지막으로 기준점부터 시작해서 모든 선분의 좌회전 여부를 확인한다.

하지만 마지막에 제외되는 점들이 있는데, 정렬한 모든 점은 전부 볼록 껍질에 포함되어 있지만 ↓ 선분에 포함되어 있는 점들의 선분은 기준점에서 봤을 때 우회전을 이루기 때문에 pop되는 듯하다. 따라서 제외된 점들을 역순으로 다시 마지막에 추가해주었다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#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;
};

LL N, X, Y;
char C;
int minX = INF;
int minY = INF;
int minI = 0;
vector<Point> Vec;
vector<Point> R;
vector<Point> Answer;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> X >> Y >> C;
        if (C == 'Y') {
            Vec.push_back({X, Y});
        }
    }
}

LL CCW(const Point &A, const Point &B, const 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(const Point &A, const Point &B) {
    LL ccwValue = CCW(Vec[0], A, B);
    if (ccwValue > 0) {
        return true;
    }
    else if (ccwValue < 0) {
        return false;
    }
    if (A.X != B.X) {
        return (A.X < B.X);
    }
    return (A.Y < B.Y);
}

void settings() {
    for (int i = 0; i < Vec.size(); i++) {
        if ((minX > Vec[i].X) || ((minX == Vec[i].X) && (minY > Vec[i].Y))) {
            minX = Vec[i].X;
            minY = Vec[i].Y;
            minI = i;
        }
    }
    Vec[minI].X = Vec[0].X;
    Vec[minI].Y = Vec[0].Y;
    Vec[0].X = minX;
    Vec[0].Y = minY;
    sort(Vec.begin() + 1, Vec.end(), Comp);
    for (int i = 0; i < Vec.size(); i++) {
        while ((Answer.size() >= 2) && (CCW(Answer[Answer.size() - 2], Answer.back(), Vec[i]) < 0)) {
            R.push_back(Answer.back());
            Answer.pop_back();
        };
        Answer.push_back(Vec[i]);
    }
    for (int i = R.size() - 1; i >= 0; i--) {
        Answer.push_back(R[i]);
    }
}

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

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

    return 0;
}