[BOJ][Python] 백준 2254번 - 감옥 건설

문제 링크: https://www.acmicpc.net/problem/2254

2254번: 감옥 건설

 

 

---

문제 풀이

볼록 껍질 문제이다. 모노톤 체인 기법으로 풀었으며, 다각형 내부의 점 판정은 CCW로 간단하게 구할 수 있다.

볼록 껍질에 대한 자세한 내용은 나중에 직접 다룰 예정이다.

볼록 껍질을 만들 수 있을 때까지 반복문을 돌려주고, 먼저 가장 먼 외각의 볼록 껍질이 완성된다. Px, Py의 좌표(점을 $P_{xy}$라고 하자.)와 만들어진 볼록 껍질로 다시 반복문을 돌린다. 이때 CCW를 이용하며, $P_{xy}$, $C_{i}$, $C_{j}$($C_{i}$, $C_{j}$는 임의의 연속된 볼록껍질의 점) 점 3개 모두가 반시계 방향이여야만 안의 점이므로 하나라도 시계 방향이라면 즉시 반복문을 종료하고 이후에 볼록 껍질을 만들어도 외각의 볼록 껍질 밖에 점이 있으므로, 볼록 껍질 만드는 반복문도 종료한다.

만약 볼록 껍질이 만들어지고 내부의 점이라면 개수에 +1을 해주자. 또한 모든 점에서 볼록 껍질이 만들어진 점을 빼려고 set을 이용하여 차집합하여 빼줬다.

 

 

코드