Convex Hull

题意翻译

**题目描述** 寻找一组点的凸包是一个重要的问题,通常是一个更大的问题的一部分。求凸包的算法有很多种。 由于涉及凸包的问题有时会出现在ACM世界总决赛,参赛者了解其中的一些算法是很有必要的。 求平面上一组点的凸包可分为两个子任务。首先,给出一个点集,找到此点集的一个子集,用线段连接,形成一个凸多边形。包含所有原始点,并使其最小。第二,按凸包顶点的顺序,绕多边形逆时针输出。在本题中,第一个子任务已经为您完成,您的程序应该完成第二个子任务。 也就是说,给定已知凸包上的顶点,按照逆时针顺序输出它们。 **输入格式** 输入的第一行包含一个整型的测试点数量。 每个测试点的第一行包含一个整数 $n(3≤n≤100000)$ 表示点数。 以下 $n$ 行每行描述一个点,包含用空格隔开的两个整数和一个字符“Y”或“N”。这两个整数指定点的 $x$ 和 $y$ 坐标。“Y”表示点是凸包的顶点,N表示不是。 各点的 $x$ 和 $y$ 坐标应不小于 $-1000000000$ 且不大于 $1000000000$ 。没有点会在同一测试点出现多次。测试点中的点永远不会都在一条线上。 **输出格式** 对于每个测试点,首先输出一行包含一个整数 $m$ 表示凸包上的顶点数。接下来输出 $m$ 行,每行描述凸包的一个顶点。每一行都应该包含这个点的 $x$ 坐标,后跟一个空格,后跟这个点的 $y$ 坐标。从 $x$ 坐标最小的点开始,以逆时针旋转。如果有多个这样的点,从 $y$ 坐标最小的点开始。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2673 [PDF](https://uva.onlinejudge.org/external/116/p11626.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11626/21a03861ec5356d39d09ad242f37cf8242e63057.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11626/a6f37a755162d84ac71a85f650153c88bc6514d7.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11626/cb0831a01da0dda3bdfd8c119109dd3cf5b104f9.png)

输入输出样例

输入样例 #1

1
5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y

输出样例 #1

4
-1 -1
1 -1
1 1
-1 1