Convex Hull

• 볼록 껍질 (Convex Hull)을 만드는 알고리즘을 알아야 될 것 같은 제목이지만, 실제로는 이미 볼록껍질을 이루는 점들이 골라져 있기 때문에, 점들을 각도 기준 정렬 만 하면 된다.
• 주의할 점은, 문제에서는 내각이 180도가 되는 꼭짓점들도 볼록껍질에 포함되어있다는 것이다. 단순 다각형 만들기에서 설명했던 것과 동일한 처리가 필요하다.
• 결국, 사실상 단순 다각형와 동일한 문제이다.

"""Solution code for "BOJ 4181. Convex Hull".

- Problem link: https://www.acmicpc.net/problem/4181
- Solution link: http://www.teferi.net/ps/problems/boj/4181

Tags: [geometry]
"""

import bisect
import math
import sys
from teflib import geometry


def main():
    n = int(sys.stdin.readline())
    points = []
    for _ in range(n):
        x, y, c = sys.stdin.readline().split()
        if c == 'Y':
            points.append([int(x), int(y)])

    pole = min(points)
    get_angle = geometry.polar_angle_key(pole)
    points.sort(key=get_angle)

    first_angle = get_angle(points[1])
    pos = bisect.bisect_right(points, first_angle, key=get_angle)
    points[1:pos] = sorted(points[1:pos], key=lambda p: math.dist(p, pole))

    last_angle = get_angle(points[-1])
    pos = bisect.bisect_left(points, last_angle, key=get_angle)
    points[pos:] = sorted(points[pos:], key=lambda p: -math.dist(p, pole))

    print(len(points))
    for p in points:
        print(*p)


if __name__ == '__main__':
    main()

• Dependency: teflib.geometry.polar_angle_key