- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- struct node
- {
- int x,y;
- };
- node vex[1000];// 存入的所有的点
- node stackk[1000];// 凸包中所有的点
- int xx,yy;
- bool cmp1(node a,node b)// 排序找第一个点
- {
- if(a.y==b.y)
- return a.x<b.x;
- else
- return a.y<b.y;
- }
- bool cmp(node a,node b)// 排序找第一个点
- {
- if(a.x==b.x)
- return a.y<b.y;
- else
- return a.x<b.x;
- }
- int cross(node a,node b,node c)// 计算叉积
- {
- return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
- }
- bool cmp2(node a,node b)// 极角排序另一种方法, 速度快
- {
- if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
- return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
- return a.x<b.x;
- }
- int main()
- {
- int t,L,n,m;
- cin>>n;
- while(n--)
- {
- cin>>m;
- int i;
- for(i=0; i<m; i++)
- {
- scanf("%d%d",&vex[i].x,&vex[i].y);
- }
- memset(stackk,0,sizeof(stackk));
- sort(vex,vex+m,cmp1);
- stackk[0]=vex[0];
- xx=stackk[0].x;
- yy=stackk[0].y;
- sort(vex+1,vex+m,cmp2);//cmp2 是更快的, cmp 更容易理解
- stackk[1]=vex[1];// 将凸包中的第两个点存入凸包的结构体中
- int top=1;// 最后凸包中拥有点的个数
- for(i=2; i<m; i++)
- {
- while(i>=1&&cross(stackk[top-1],stackk[top],vex[i])<0) // 对使用极角排序的 i>=1 有时可以不用, 但加上总是好的
- top--;
- stackk[++top]=vex[i]; // 控制 < 0 或 <=0 可以控制重点, 共线的, 具体视题目而定.
- }
- sort(stackk,stackk+top+1,cmp);
- for(i=0;i<=top;i++)
- printf("%d %d\n",stackk[i].x,stackk[i].y);
- }
- }
来源: http://www.bubuko.com/infodetail-2729530.html