[백준] 1708.볼록 껍질

문제

 

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

1708번: 볼록 껍질

다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (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

 

 

 

문제풀이 코드

import sys
input = sys.stdin.readline

def ccw(A, B, C):
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
n = int(input())
points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append([x, y])

# 시계 반대방향으로 정렬 시작
points.sort()
start = points[0]
points.remove(start)

inf = []
for i in range (n-1):
    if start[0] == points[i][0]:
        # 시작점와 같은 y축에 있는 좌표는 따로 빼준다
        inf.append(points[i])
    else:
        # 두 점사이에 기울기를 추가
        points[i].append((start[1]-points[i][1])/(start[0]-points[i][0]))

for i in inf:
    points.remove(i)
# 기울기를 기준으로 정렬
points.sort(key=lambda x : x[2])

for i in inf:
    points.append(i)
# 정렬 종료

stack = []

stack.append(start)
stack.append(points[0])

# Convex Hull(Graham's Scan)
for i in range(1, len(points)):
    # 평행을 이루고 있거나, 시계방향으로 갈 때는 스택에서 제거한다.
    while len(stack) >= 2 and ccw(stack[-2], stack[-1], points[i]) <= 0:
        stack.pop()
    stack.append(points[i])

print(len(stack))

이전엔 Monotone Chain 알고리즘을 사용하여 Convex Hull 문제를 해결했고, 이번 문제는 Graham's Scan 알고리즘을 사용하여 문제를 해결했다. ccw를 이용한 스캔과정을 이전과 유사하나, 위 아래로 탐색하는것이 아니기 때문에 중복되는 좌표를 제거하지 않아도 된다.

1. 그레이엄 스캔을 시작하기 이전에 모든 점은 시계 반대방향으로 정렬되어 있어야 한다.

2. 시작지점을 가져오기 위해서 x축을 기준으로 점들을 정렬한다.

3. 첫번째에 있는 점을 시작포인트로 가져오고, 배열에서 제거한다.

4. 시계 반대방향으로 정렬하기 위해서, 시작점과 points[i]의 기울기를 구하여 추가해준다.(시작점과 y좌표가 같은 점들은 따로 빼둠)

5. 추가된 기울기를 기준으로 배열을 정렬하면 시계 반대방향으로 정렬하게 되고, 이전에 제거했던 시작점과 y좌표가 같은 점을 추가

6. 해당 문제는 한 직선에 점은 두개만 있으면 되기 때문에 ccw에서 받은 값이 0보다 작거나 같을 때 스택에서 pop해준다.

7. 반복문이 종료되면 스택에는 볼록껍질에 해당하는 점만 들어가있기 때문에 스택의 길이를 반환한다.