[백준] 4181.Convex Hull

문제

 

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

4181번: Convex Hull

문제

때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소양이 되었다.

이 작업은 크게 두 단계의 과정으로 이루어진다. 첫 번째 단계는 볼록 껍질을 이루는 점들을 찾아내는 것이고, 두 번째 단계는 이 점들을 반시계 방향으로 순서를 매기는 것이다. 첫 번째 단계는 이미 완료되었다고 할 때, 두 번째 단계를 수행하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에는 점의 개수 n이 주어진다. (3 <= n <= 100,000)

두 번째 줄부터 n개의 줄에 걸쳐 각 점에 대한 정보 x, y, c가 주어진다. x, y는 정수이며 절댓값이 1,000,000,000을 넘지 않고, c는 Y 또는 N인 문자이다. Y는 이 점이 볼록 껍질에 속해있음을, N이면 아님을 의미한다.

중복되는 점은 없으며, 모든 점이 한 직선 위에 있는 경우도 없다.

 

출력

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

이어서 한 줄에 하나씩 그 점들의 좌표를 x y 형태로 출력하는데, 이 점들은 반시계 방향으로 순서를 이루어야 한다. 첫 번째 좌표는 x좌표가 가장 작은 점이어야 하며, 만약 그런 좌표가 여러 개라면 그 중에서 y좌표가 가장 작은 점을 선택한다.

 

예제

입력	출력
5 1 1 Y 1 -1 Y 0 0 N -1 -1 Y -1 1 Y	4 -1 -1 1 -1 1 1 -1 1

 

 

문제풀이 코드

import sys
from itertools import chain
input = sys.stdin.readline

N = int(input())

# 세 점의 방향 관계를 구함(반시계방향)
def ccw(A, B, C):
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])

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

points.sort()
stack = []

# Monotone Chain
for i in chain(range(len(points)), reversed(range(len(points) - 1))):
    while len(stack) >= 2 and ccw(stack[-2], stack[-1], points[i]) < 0:
        stack.pop()
    stack.append(points[i])
    
# 중복 껍질 제거
stack.pop()
for i in range(1, (len(stack) + 1) // 2):
    if stack[i] != stack[-1]:
        break
    stack.pop()

print(len(stack))
for s in stack:
    print(s[0], s[1])

해당 문제는 볼록껍질에 속해있는 좌표를 알 수 있지만 모든 좌표가 주어졌기 때문에 전체 좌표에서 볼록껍질에 해당하는 부분을 구하여 반환하는 방법으로 문제를 해결했고, ConvexHull 알고리즘 중에 Monotone Chain을 이용하였다. 이유는 Graham's Scan은 좌표를 반시계방향으로 정렬해야하는 과정을 거쳐야하기 때문에 좀 더 간단한 Monotone Chain을 사용하기로 했다.

1. Monotone Chain은 껍질의 윗방향과 아랫방향을 만들어 합치기 때문에 chain을 이용하여 반복문을 (0 ~ n ~ 0)으로 돌도록 만든다.

2. stack에는 ccw로 체크를 하기위해 최소 2개의 좌표가 들어가있어야 한다.

3. ccw의 결과가 시계방향이면 0보다 작은값, 평행하면 0, 시계 반대방향이면 0보다 큰 값을 반환한다.

4. stack[-2], stack[-1], points[i]를 A, B, C로 두고 해당 좌표들이 시계 반대방향으로 돌고있으면 현재 좌표를 스택에 넣어주고

5. 세 좌표가 조건을 만족하지 못하면 stack에 있는 값을 하나씩 뽑아준다.

6. 좌표를 구하는 과정이 종료되면 Monotone Chain 알고리즘은 위아래를 합치는 것이기 때문에 중복된 껍질을 제거한다.

7. 마지막으로 스택에 들어있는 좌표들의 수와 순서대로 좌표를 출력한다.