[백준 1708번] 볼록 껍질 (Python3)

import sys,math
input = sys.stdin.readline

N = int(input())

point = []
for _ in range(N):
  x,y = map(int,input().split())
  point.append((y,x))
point.sort()

cospoint = []
sy,sx = point[0]
for i in range(1,N):
  y,x = point[i]
  cospoint.append(((sx-x)/math.sqrt((x-sx)**2+(y-sy)**2),x,y))
cospoint.sort()
convex = [(sx,sy)]

for i in range(N-1):
  cos,x,y = cospoint[i]
  while len(convex)>1:
    x1,y1,x2,y2 = *convex[-2],*convex[-1]
    CCW = (x1-x2)*(y-y2)-(y1-y2)*(x-x2)
    if CCW > 0:
      convex.pop()
    elif CCW == 0:
      if (sx-x2)**2+(sy-y2)**2 > (sx-x)**2+(sy-y)**2:
        x,y = convex.pop()
      else:
        convex.pop()
    else:
      break
  convex.append((x,y))

x1,y1,x2,y2 = *convex[-2],*convex[-1]
CCW = (x1-x2)*(sy-y2)-(y1-y2)*(sx-x2)
if CCW == 0:
  convex.pop()

print(len(convex))

볼록껍질 기본 문제이다.

기본 문제인데 구현하기가 굉장히 어려웠다.

 

알고리즘은 그레이엄 스캔 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 이걸 참조하였다.

1. y와 x좌표가 가장 작은 점을 시작점으로 잡는다.

2. y,x에 대해서 x축과의 각도를 작은 순으로 나열 (이때 cos을 이용하였다. y가 가장 작은 값으로 잡았기 때문에 cos값이 음수가 될일이 없기 때문)

3. 2에서 정렬한 점에 대해서 순서대로 convex 리스트에 쌓음. 이때 CCW가 양수인 경우 이전의 값을 pop한다.

4. CCW가 0인 경우 시작점과의 거리에 따라서 제거해주어야 한다.

5. 가장 마지막에는 마지막 두 점과 첫번째 점과의 CCW가 0인지를 체크, 0이면 pop해준다.

 

 

알고리즘 자체는 크게 어려울 것이 없는데, CCW가 0일때 처리방법이 어려웠다.

처음에는 그냥 0일때와 양수일때 모두 pop해주면 된다고 생각했는데, 그게 아니라는 것을 알게되었다.

 

어쨌든 새로운 알고리즘을 배웠으니 이를 활용해서 여러가지 문제를 풀어보아야겠다

 

 

오늘의 교훈) 볼록껍질에서 CCW = 0일때 조심!