난이도

Platinum 5

인증

문제

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.

조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.

2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.

출력

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.

예제 입력

8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2

예제 출력

5

해설 및 후기

볼록 껍질을 이루는 점들의 위치를 찾아내는 과정에서 ccw함수를 이용해 예각인지를 판별하고자 했다. 주로 사용되는 방법이 그레이엄 스캔이라고 하는데, 어떤 한 점을 기준으로(보통 y가 가장 낮은 점) 반시계방향으로 점을 정렬해야 한다. 그러나, 파이썬에서는 이러한 정렬이 쉽진 않아서 모노톤 정렬이라고 하는, x가 가장 작은 점을 기준으로 윗 볼록 껍질과 아래 볼록 껍질을 나누어 구하는 방식을 이용하였다.

제출 코드

import sys
import math
n = int(sys.stdin.readline().rstrip())

def ccw(a,b,c):
    res = (b[0]-a[0])*(c[1]-a[1]) - (c[0]-a[0])*(b[1]-a[1])
    if(res < 0):
        return -1
    elif(res > 0):
        return 1
    else:
        return 0

lsts = []
for i in range(n):
    x,y = map(int,sys.stdin.readline().rstrip().split())
    lsts.append([x,y])

lsts = sorted(lsts, key=lambda x:(x[0], x[1]))
cnt = 0
stk = []
for point in lsts:
    while(len(stk)>1 and ccw(stk[-2], stk[-1], point)<=0):
          stk.pop()
    stk.append(point)
cnt += len(stk)
stk = []
for point in lsts:
    while(len(stk)>1 and ccw(stk[-2], stk[-1], point)>=0):
          stk.pop()
    stk.append(point)
cnt += len(stk)

print(cnt-2)