题意分析

本题要求计算平面上给定点集的凸包，并按指定的标准顺序输出凸包的顶点。凸包是包含所有点的最小凸多边形，顶点为点集中的点。标准顺序的定义如下：

1. 起点选择：选择y坐标最大的点，若y相同则选择x最小的点作为第一个顶点。
2. 顺时针排序：顶点按顺时针顺序围绕凸包排列。

解题思路

1. 凸包算法选择

采用Andrew算法（凸包扫描法），步骤如下：

• 排序：先按x坐标升序排序，x相同则按y升序排序，得到下凸包的点序列。
• 构建下凸包：从左到右遍历点，维护一个栈，确保栈中的点构成下凸包（相邻三点形成的向量叉积非负，保证顺时针）。
• 构建上凸包：从右到左遍历点（跳过已加入下凸包的最后一个点），同样维护栈，确保形成上凸包（相邻三点叉积非负）。
• 合并结果：合并下凸包和上凸包，去重得到完整凸包顶点。

2. 标准顺序调整

Andrew算法得到的凸包顶点是按逆时针顺序排列的，需转换为顺时针顺序，并调整起点为标准顺序的第一个顶点：

1. 找到标准起点：遍历凸包顶点，找到y最大（x最小）的点。
2. 顺时针排序：以标准起点为基准，将凸包顶点按顺时针顺序排列。可通过计算各点相对于起点的极角，并按极角从大到小排序（顺时针方向）。

3. 极角排序方法

以标准起点为原点，计算其他点的极角（与x轴正方向的夹角）。顺时针排序等价于极角从大到小排列，可通过叉积判断点的相对位置。

实现步骤

1. 输入处理：读取点集，存储为坐标列表。
2. 凸包计算：
   • 使用Andrew算法构建凸包，得到逆时针顺序的顶点列表。
3. 标准起点定位：遍历凸包顶点，找到y最大（x最小）的点作为起点。
4. 顺时针排序：
   • 将起点移至列表开头，其余点按相对于起点的极角从大到小排序（使用叉积判断顺序）。
5. 输出结果：按顺序输出凸包顶点，确保格式正确。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN=64;
 
struct P
{
	int x,y;	
}pnt[maxN],cnt[maxN];
int n;
 
int cmp(P a,P b)
{
	if(a.y!=b.y)
		return a.y<b.y;
	return a.x<b.x;
}
 
int cross(P a,P b,P c)
{
	int x1=b.x-a.x;
	int y1=b.y-a.y;
	int x2=c.x-a.x;
	int y2=c.y-a.y;
	return x1*y2-x2*y1;
}
int graham()
{
	sort(pnt,pnt+n,cmp);
	int i,pos=1;
	cnt[0]=pnt[0];
	cnt[1]=pnt[1];
	for(i=2;i<n;++i){
		while(pos>0&&cross(cnt[pos-1],cnt[pos],pnt[i])<=0) --pos;
		cnt[++pos]=pnt[i];		
	}
	int bak=pos;
	for(i=n-2;i>=0;--i){
		while(pos>bak&&cross(cnt[pos-1],cnt[pos],pnt[i])<=0) --pos;
		cnt[++pos]=pnt[i];
	}			
	return pos;
}
 
int main()
{
	int cases,case_num;
	scanf("%d",&cases);
	while(cases--){
		scanf("%d%d",&case_num,&n);	
		int pos;
		for(int i=0;i<n;++i)
			scanf("%d%d",&pnt[i].x,&pnt[i].y);
		printf("%d %d\n",case_num,pos=graham());		
		int index=0;
		for(int i=1;i<pos;++i)
			if(cnt[i].y>cnt[index].y)
				index=i;
			else if(cnt[i].y==cnt[index].y&&cnt[i].x<cnt[index].x)
				index=i;
		int mod=pos;
		while(pos--){
			printf("%d %d\n",cnt[index].x,cnt[index].y);
			--index;
			index+=mod;
			index%=mod;	
		}
	}
	return 0;	
}