[Python]4181-Convex Hull

www.acmicpc.net/problem/4181

4181번: Convex Hull

그냥 monotone chain알고리즘 돌려서 볼록껍질 구해서 차례대로 출력하면 된다.

(정렬은 x오름차순, y오름차순으로)

주의할 것은 볼록껍질을 이루는 몇몇 점이 한선분 위에 있고, 그 선분이 볼록껍질을 이룰때, 사이의 점도 출력해줘야 한다는 것이다.

import sys
input = sys.stdin.readline
n = int(input())
dots = []
dA = dots.append
for _ in range(n):
    x,y,c = input().split()
    if c == 'Y':
        dA([int(x), int(y)])

def ccw(p1, p2, p3):
    return p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])

def monotoneChain(dots):
    dots.sort()

    lower = []
    for d in dots:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], d) < 0:
            lower.pop()
        lower.append(d)

    upper = []
    for d in reversed(dots):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], d) < 0:
            upper.pop()
        upper.append(d)
    return lower[:-1] + upper[:-1]
res = monotoneChain(dots)
print(len(res))
for x,y in res:
    print(f'{x} {y}')

밑에 틀린 이유는 사이의 점을 출력하지 않아 틀렸다. 왜 틀렸는지 꽤 오래 고민헀는데 좀 허무하다.