eolymp
bolt
Try our new interface for solving problems
Problems

Convex Hull

Convex Hull

\includegraphics{https://static.e-olymp.com/content/79/7913cb36340b423d9e084d35c5564c08ba525c23.jpg} Finding the convex hull of a set of points is an important problem that is often part of a larger problem. There are many algorithms for finding the convex hull. Since problems involving the convex hull sometimes appear in the ACM World Finals, it is a good idea for contestants to know some of these algorithms. Finding the convex hull of a set of points in the plane can be divided into two sub-tasks. First, given a set of points, find a subset of those points that, when joined with line segments, form a convex polygon that encloses all of the original points. Second, output the points of the convex hull in order, walking counter-clockwise around the polygon. In this problem, the first sub-task has already been done for you, and your program should complete the second sub-task. That is, given the points that are known to lie on the convex hull, output them in order walking counter-clockwise around the hull. \InputFile The first line of input contains a single integer \textbf{3} ≤ \textbf{n} ≤ \textbf{100000}, the number of points. The following \textbf{n} lines of input each describe a point. Each of these lines contains two integers and either a \textbf{Y} or an \textbf{N}, separated by spaces. The two integers specify the \textbf{x}- and \textbf{y}-coordinates of the point. A \textbf{Y} indicates that the point is on the convex hull of all the points, and a \textbf{N} indicates that it is not. The \textbf{x}- and \textbf{y}-coordinates of each point will be no less than \textbf{-1000000000} and no greater than \textbf{1000000000}. No point will appear more than once in the input. The points in the input will never all lie on a line. \OutputFile First, output a line containing a single integer \textbf{m}, the number of points on the convex hull. Next output \textbf{m} lines, each describing a point on the convex hull, in counter-clockwise order around the hull. Each of these lines should contain the \textbf{x}-coordinate of the point, followed by a space, followed by the \textbf{y}-coordinate of the point. Start with the point on the hull whose \textbf{x}-coordinate is minimal. If there are multiple such points, start with the one whose \textbf{y}-coordinate is minimal.
Time limit 1 second
Memory limit 64 MiB
Input example #1
5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y
Output example #1
4
-1 -1
1 -1
1 1
-1 1