볼록 껍질

주어진 점들의 볼록 껍질(convex hull)을 찾는 기술은 여러 곳에서 요긴하게 쓰입니다. 이 작업은 크게 두 단계로 나뉩니다. 첫 번째 단계는 볼록 껍질 위에 있는 점들을 찾아내는 것이고, 두 번째 단계는 그 점들을 반시계 방향 순서로 나열하는 것입니다. 첫 번째 단계는 이미 끝났다고 가정합니다. 즉, 각 점이 볼록 껍질 위에 있는지 아닌지가 이미 표시되어 있습니다. 두 번째 단계를 수행하는 프로그램, 곧 볼록 껍질 위의 점들을 반시계 방향으로 나열하는 프로그램을 작성하세요.

첫째 줄에 점의 개수 $n$이 주어집니다 ($3 \le n \le 100{,}000$).

다음 $n$개의 줄에는 각 점에 대한 세 값 $x$, $y$, $c$가 주어집니다. $x$와 $y$는 절댓값이 $1{,}000{,}000{,}000$ 이하인 정수이고, $c$는 문자 Y 또는 N입니다. Y는 그 점이 볼록 껍질 위에 있음을, N은 그렇지 않음을 뜻합니다.

같은 위치의 점은 없으며, 모든 점이 한 직선 위에 있는 경우도 없습니다.

첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력합니다. 이어서 그 점들을 한 줄에 하나씩 x y 형태로, 반시계 방향 순서가 되도록 출력합니다. 가장 먼저 출력하는 점은 $x$좌표가 가장 작은 점이어야 하며, 그런 점이 여럿이라면 그중에서 $y$좌표가 가장 작은 점을 고릅니다.