题目描述

给你一个二维平面点集，求解其凸包，凸包是指一个最小凸多边形，满足集合中的点或者在多边形边上或者在其内。 如果点集上所有点都在一条直线上，那么凸包会退化为一条线段，见图右下角

找到凸包的顶点后，从纵坐标y最大的顶点开始顺时针输出凸包上的所有顶点。 1.若纵坐标y有多个最大值，选用横坐标x小的那个顶点作为起始顶点。 2.并非凸包上所有的点都是顶点。

输入格式

输入一个整数T，代表有T个点集1 接下来给出T个点集的信息 每个点集信息的第一行包括两个整数m和n，表示点集的编号和点集含有的点的数量（3 接下来依次给出n个点的信息，每个信息包含x，y两个整数，代表该点的横坐标与纵坐标，每行最多包含5组点的信息

输出格式

第一行输出该点集的编号和凸包上顶点的数量N 接下来N行输出每个顶点的信息

4 
1 25 
2 1 7 1 1 2 9 2 1 3 
10 3 1 4 10 4 1 5 10 5 
2 6 10 6 2 7 9 7 3 8 
8 8 4 9 7 9 6 2 3 3 
5 4 7 5 8 6 4 6 3 7 
2 30 
3 9 6 9 3 8 9 8 3 7 
12 7 2 6 12 6 2 5 12 5 
2 4 12 4 1 3 11 3 1 2 
11 2 1 1 11 1 1 0 10 0 
4 -1 10 -1 7 -2 10 -2 5 0 
7 3 4 5 6 8 3 1 2 6 
3 3 
3 1 2 2 1 3 
4 6 
1 3 19 1 4 2 2 1 11 2 
10 1

1 10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
2 8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
3 2
1 3
3 1
4 4
1 3
11 2
19 1
2 1