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를 체크하기 위해 한번 더 돌았기 때문)
오늘의 교훈) 볼록껍질 알고리즘에 익숙해지자