====== Convex Hull ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:geometry#polar_angle_key|teflib.geometry.polar_angle_key]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}