백준 4181 (C++) Convex Hull

최초 업로드: 2025-08-17 21:50:38

최근 수정 시간: 2025-08-17 21:51:02

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] Convex Hull

[문제 링크](https://www.acmicpc.net/problem/4181)

## 문제 설명

때때로 주어진 점들 사이에서 볼록 껍질(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좌표가 가장 작은 점을 선택한다.

## 풀이
#### 반시계 방향으로 각도 정렬한 후, 원점에서의 벡터값이 같은 마지막 점들이 반대로 정렬되는 경우를 반대로 뒤집어주어 예외 처리 해주었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct point {
 ll x, y, p=0, q=0;
 bool operator<(const point o) const {
 if(p*o.q!=o.p*q) return p*o.q > o.p*q;
 if(x!=o.x) return x < o.x;
 return y < o.y;
 }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

vector<point> v;
 while(n--) {
 ll x, y; char c; cin >> x >> y >> c;
 if(c=='Y') v.push_back({x, y});
 }
 sort(v.begin(), v.end());

for(int i=1;i<v.size();i++) {
 v[i].p = v[i].x - v[0].x;
 v[i].q = v[i].y - v[0].y;
 }
 sort(v.begin(), v.end());

int last=v.size()-1; // 원점에서 각도가 같은 마지막 점들 반대로 정렬되는 것 예외처리
    for(int i=v.size()-2;i>=0;i--) {
        if(v[i].p*v[last].q!=v[i].q*v[last].p) {
            reverse(&v[i+1], &v[last+1]);
            break;
        }
    }

cout << v.size() << '\n';
 for(auto e : v) cout << e.x << ' ' << e.y << '\n';
}
```