[백준 2254번] 감옥 건설 (Python3)

import sys,math
input = sys.stdin.readline
from heapq import *

def CCW(y1,x1,y2,x2,y3,x3):
  return (x1-x2)*(y3-y2)-(x3-x2)*(y1-y2)

def convexhull():
  global co
  if not co:
    return
  inside = False
  y,x = co[0]
  if y==Py and x==Px:
    inside = True
  convex = [(y,x)]; newco = []
  hq = []
  for i in range(1,len(co)):
    yi,xi = co[i]
    d = math.sqrt((x-xi)**2+(y-yi)**2)
    heappush(hq,((x-xi)/d,d,yi,xi))
  while hq:
    cos,d,yi,xi = heappop(hq)
    if yi==Py and xi==Px:
      inside = True
    while len(convex) > 1:
      ccw = CCW(*convex[-2],*convex[-1],yi,xi)
      if ccw < 0:
        break
      if ccw == 0:
        convex.pop()
      else:
        newco.append(convex.pop())
    convex.append((yi,xi))
  co = sorted(newco)
  return inside

N,Px,Py = map(int,input().split())
co = [(Py,Px)]
for i in range(N):
  x,y = map(int,input().split())
  co.append((y,x))
co.sort()
result = -1
while convexhull():
  result += 1
print(result)

볼록껍질 [백준 1708번] 볼록 껍질 (Python3) (tistory.com) 문제이다.

아이디어는 쉬웠는데, 볼록껍질 알고리즘이 익숙지 않은 탓에 구현하기가 좀 까다로웠다.

 

볼록껍질 알고리즘을 알고 있다는 가정 하에 풀이를 설명하면,

1. 가장 바깥에서부터 볼록껍질로 내부를 싼다. 이때 CCW=0이 되는 점은 버리고, CCW>0인 점, (즉 볼록껍질에 포함되지 않는 점) 은 다시 저장한다.

2. 1에서 저장한 볼록껍질에 쓰이지 않은 점들로 다시 볼록껍질을 싼다.

3. 볼록껍질 과정에서 점들 중에 Px,Py가 있는지를 체크한다. Px,Py가 있으면 inside = True이며, 볼록껍질을 계속 반복한다.

4. inside = False이면 이전의 볼록껍질에 Px,Py가 포함되었다는 뜻이다. break 한다.

5. 볼록껍질 횟수-1을 출력한다. (-1을 하는 이유는 inside를 체크하기 위해 한번 더 돌았기 때문)

 

 

오늘의 교훈) 볼록껍질 알고리즘에 익숙해지자