난이도

Platinum 5

인증

문제

때때로 주어진 점들 사이에서 볼록 껍질(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

예제 출력

해설 및 후기

이름이 Convex Hull이라 볼록 껍질과 아예 같은 문제인 줄 알았지만 다른 문제였다. 그러나 방식은 유사하다. 이 문제는 컨벡스 헐을 구하는 문제가 아니라, 구해져 있는 컨벡스 헐 점들을 어떻게 그레이엄 스캔을 위한 정렬을 수행할 것인가? 이다. 이전에 구한 볼록 껍질의 점들은 일직선일 때를 완전히 무시했지만, 이번 경우에는 볼록 껍질이 되는 모든 점들을 허용하기 위해 일직선인 점도 포함하도록 모노톤 알고리즘을 변형하고, 이를 다시 순서대로 정렬하여 답을 구했다.

제출 코드

import sys
from math import atan2
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,k = sys.stdin.readline().rstrip().split()
    if(k == 'Y'): # 해당하는 것들만
        lsts.append([int(x),int(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): # 이전 모노톤 알고리즘의 변형 - ccw 값이 0인 경우도 허용한다. 즉 직선도 허용
          stk.pop()
    stk.append(point)
cnt += len(stk)
tmpStk = 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)
for x,y in tmpStk:
    print(x,y)
for x,y in list(reversed(stk))[1:-1]:
    print(x,y)