백준 2254 (C++) 감옥 건설

최초 업로드: 2025-08-12 14:20:40

최근 수정 시간: 2025-08-12 17:43:18

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 감옥 건설

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

## 문제 설명

소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다. 소들은 (Px, Py)의 위치에 감옥을 짓고, 감옥 둘레에 가능한 한 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려 한다. 감옥은 하나의 점으로 표현된다.

이러한 목적을 달성하기 위해, 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다. 즉, 담벼락이 교차하거나 한 점에서 만나서는 안 된다. 감옥과 담 기둥 중 어느 세 점도 일직선상에 있지 않다.

이러한 담 기둥들이 주어졌을 때, 겹치지 않는 최대의 중첩된 담의 겹 수를 구하는 프로그램을 작성하시오.

담은 여러 개의 담벼락이 연결된, 닫힌 다각형을 의미하고, 각각의 담벼락의 두 끝 점은 담 기둥 이어야 한다. 이러한 담 사이에는 반드시 약간이라도 공간이 있어야 한다. 즉, 서로 다른 두 담이 하나의 담벼락이나 담 기둥을 공유해서는 안 된다.

## 입력

첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.

## 출력

첫째 줄에 최대 겹 수를 출력한다.

## 풀이
#### 그라함 스캔으로 매번 모든 점을 포함하는 볼록 다각형을 만들어주었다. 감옥이 이 볼록 다각형 안에 있는지는 볼록 다각형을 이루는 모든 직선에 대해 ccw를 사용해 반시계 방향에만 있는 지로 확인하였다.

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

typedef long long ll;

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

ll n;
pos P;

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

bool isInside(vector<int> stk, vector<pos> v) {
 if(stk.size()<=2) return false;
 for(int i=0;i<stk.size();i++) {
 if(ccw(v[stk[i]], v[stk[(i+1)%stk.size()]], P)<=0) return false;
 }
 return true;
}

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

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

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

cnt++;
 for(int i=stk.size()-1;i>=0;i--) {
 v.erase(v.begin()+stk[i]);
 }
 n = v.size();
 }
 cout << cnt;
}
```