Convex Hull

볼록껍질을 이루는 점의 갯수와 그 점들의 좌표를 반시계 방향 순서로 출력한다.

볼록 껍질 문제랑 비슷하다.

볼록 껍질을 이루는 좌표만 가지고 convex hull을 만든 다음 순서대로 출력하면 된다.

import sys
input = sys.stdin.readline

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

def convex_hull(points):
    points = sorted(points)
    lower = []
    for p in points:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) < 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) < 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

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

print(len(convex_hull(points)))
for p in convex_hull(points):
    print(p[0], p[1])