Convex Hull#2294
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 ACM programming world championships, 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 counterclockwise around the polygon. In this problem, the first sub-task has already been completed 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 counterclockwise around the hull.
The first line of input contains a single integer 3 \le n \le 100000, the number of points. The following lines each describe a point. Each of these lines contains two integers and either a Y or a N, separated by spaces. The two integers specify the - and -coordinates of the point. A Y indicates that the point is on the convex hull of all the points, and a N indicates that it is not. The - and -coordinates of each point will be no less than and no greater than . No point will appear more than once in the input. The points in the input will never all lie on a line.
First, output a line containing a single integer , the number of points on the convex hull. Next, output lines, each describing a point on the convex hull, in counterclockwise order around the hull. Each of these lines should contain the -coordinate of the point, followed by a space, followed by the -coordinate of the point. Start with the point on the hull whose -coordinate is minimal. If there are multiple such points, start with the one whose -coordinate is minimal.
Example 1