[BOJ 2254] 감옥 건설

문제

---

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

풀이

---

한 점을 포함하는, 겹치지 않는 볼록 껍질을 최대 몇 개까지 만들 수 있는지 묻는 문제이다.

1. 볼록 껍질을 구한다.

2. 그 안에 감옥이 있는지 확인한다.

3. 있다면 볼록 껍질을 이루는 점들을 제거하고 1번으로 돌아간다.
   없다면 지금까지 만든 볼록 껍질의 수를 반환한다.

이 풀이의 정당성은 귀류법으로 증명할 수 있다.

만약 2번 과정에서 감옥이 볼록 껍질 밖에 있지만, 감옥을 포함하는 다각형을 하나 이상 만들 수 있다고 가정하자.

볼록 껍질 내부 영역을 P, 감옥을 포함하는 다각형의 내부 영역을 S라고 하자.

볼록 껍질의 정의에 의해, 감옥 $ \in $ S $ \subseteq $ P이 성립하고 이는 감옥 $ \in $ P에 모순이다.

감옥이 볼록 껍질 내에 있는지 확인하려면, CCW를 계산해 줌으로써 확인할 수 있다.

코드

---

import sys


def tangent(x, y):
    if x == a:
        return 1, y
    if x > a:
        return 0, (y - b) / (x - a), x
    if x < a:
        return 2, (y - b) / (x - a), x


def isline(x, y, z):
    return (y[1] - x[1]) * (z[0] - y[0]) == (z[1] - y[1]) * (y[0] - x[0])


n, px, py = map(int, sys.stdin.readline().split())
coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
if n <= 2:
    print(0)
    exit()

res = 0
while len(coord) >= 3:
    coord.sort(key=lambda x: (x[1], x[0]))
    a, b = coord.pop(0)
    coord.sort(key=lambda x: tangent(x[0], x[1]))

    stack = [(a, b), coord[0]]
    idx = 0
    while idx < len(coord) - 1:
        idx += 1
        w1, w2 = coord[idx]
        while len(stack) >= 2:
            u1, u2 = stack[-2]
            v1, v2 = stack[-1]
            if (v1 - u1) * (w2 - v2) <= (v2 - u2) * (w1 - v1):
                stack.pop()
            else:
                break
        stack.append((w1, w2))
        if (len(stack) >= 3) and (isline(stack[-3], stack[-2], stack[-1])):
            stack.pop(-2)

    if len(stack) >= 3:
        if isline(stack[-2], stack[-1], stack[0]):
            stack.pop()

    for i in range(len(stack)):
        u1, u2 = stack[i]
        v1, v2 = stack[(i + 1) % len(stack)]
        if (u1 - px) * (v2 - py) < (v1 - px) * (u2 - py):
            break
    else:
        res += 1
        for point in stack:
            if point != (a, b):
                coord.remove(point)
        continue
    
    break

print(res)