백준 1708 (C++) 볼록 껍질

최초 업로드: 2025-08-11 16:55:31

최근 수정 시간: 2025-08-11 16:55:58

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] 볼록 껍질

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

## 문제 설명

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.

## 출력

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

볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.

## 풀이
#### 그라함 스캔을 써서 풀었다.

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

typedef long long ll;

struct pos {
 ll x, y;
 ll p=0, q=0; // 기준점으로부터의 상대 위치
 bool operator<(const pos b) const {
 if(p*b.q!=q*b.p) return p*b.q > q*b.p;
 if(y!=b.y) return y < b.y;
 return x < b.x;
 }
};

ll ccw(pos a, pos b, pos c) {
    pos vec1 = {b.x-a.x, b.y-a.y};
    pos vec2 = {c.x-b.x, c.y-b.y};
    return vec1.x*vec2.y - vec1.y*vec2.x;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 vector<pos> v(n);
 for(int i=0;i<n;i++) cin >> v[i].x >> v[i].y;
 sort(v.begin(), v.end());

// y가 가장 작고 x가 가장 작은 점을 기준점으로 삼고, 시계 반대 방향으로 정렬
 for(int i=0;i<n;i++) {
 v[i].p = v[i].x-v[0].x;
 v[i].q = v[i].y-v[0].y;
 }
 sort(v.begin(), v.end());

vector<pos> stk;
 for(int i=0;i<n;i++) {
 if(stk.size()<2) {
 stk.push_back(v[i]);
 } else {
 while(stk.size()>=2 && ccw(stk[stk.size()-2], stk[stk.size()-1], v[i])<=0) {
 stk.pop_back();
 }
 stk.push_back(v[i]);
 }
 }
 cout << stk.size();
}
```