//Memory Time // 1347K 0MS // by : Snarl_jsb #include<algorithm> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<vector> #include<queue> #include<stack> #include<map> #include<string> #include<climits> #include<cmath> #define MAX 1100 #define N 1000 #define INF 1000000 #define LL long long using namespace std; struct point { int x,y; //横纵坐标 : x,y double len,theta; //与参考点的距离 len 与参考点构成的向量与 (1,0)向量构成的夹角的余弦值 theta }g[N]; //定义了一个全局变量,记录凸包中的点 /*--------按余弦值,从大到小快速排序--------*/ void qsort(int st,int en) { int i=st,j=en; g[0]=g[i]; while(i<j) { while(i<j && g[0].theta>=g[j].theta) j--; if(i<j) { g[i]=g[j]; i++; } while(i<j && g[0].theta<=g[i].theta) i++; if(i<j) { g[j]=g[i]; j--; } } g[i]=g[0]; if(st<i-1) qsort(st,i-1); if(i+1<en) qsort(i+1,en); } /*-----------Graham 扫描法-------------*/ void graham(int *n) { /*第一步,寻找y坐标最小,然后x坐标最小的点*/ int p=1; for(int i=2;i<=*n;i++) if((g[i].y<g[p].y)||(g[i].y==g[p].y && g[i].x<g[p].x)) p=i; g[0]=g[p]; g[p]=g[1]; g[1]=g[0]; /*找到该点,并把它存放在 g 中的第一个元素的位子上*/ /*第二步,计算所有的点距离参考点的距离(len) 还有夹角的余弦值 (theta)*/ for(int i=2;i<=*n;i++) { g[i].len=sqrt((g[i].x-g[1].x)*(g[i].x-g[1].x)+(g[i].y-g[1].y)*(g[i].y-g[1].y)); g[i].theta=100*(g[i].x-g[1].x)/g[i].len; } qsort(2,*n);//先根据夹角的余弦值从大到小排序 /*第三步,将所有theta值相等的点,只保存len值最大的,存放在数组map中*/ point map[N]; int tot=0; p=1; while(p<=*n) { int k=p; while(fabs(g[p].theta-g[p+1].theta)<=1e-6) { if(g[p+1].len>g[k].len) k=p+1; p++; } map[++tot]=g[k]; p++; } /*第四步,对map中的元素扫描一遍,确定凸包的元素,放在数组g中*/ *n=tot; tot=3; //先做了一个小小的处理,使得自己更好理解 memset(g,0,sizeof(g)); g[1]=map[1]; g[2]=map[2]; g[3]=map[3]; //先将前三个点入栈 g for(int i=4;i<=*n;i++) //依次用map中的每个点对g中的点进行一次判断,看是否是属于凸包 { double chaji=(g[tot].x-g[tot-1].x)*(map[i].y-g[tot].y)-(map[i].x-g[tot].x)*(g[tot].y-g[tot-1].y); for(;chaji<=0 && tot>=1;) //如果旋转的方向不同,g[tot]这个点就不是,删除,并继续判断 g 中下一个点是不是 { tot--; chaji=(g[tot].x-g[tot-1].x)*(map[i].y-g[tot].y)-(map[i].x-g[tot].x)*(g[tot].y-g[tot-1].y); } g[++tot]=map[i]; //将map[i]这个点入栈,至于是否是属于凸包中的点,等待以后的点来判断 } *n=tot;//凸包处理完,总共有tot个凸包上的点 } int main() { //freopen("C:/Users/chengfeng/Desktop/in.txt","r",stdin); int n; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d%d",&g[i].x,&g[i].y); graham(&n); for(int i=1;i<=n;i++) printf("(%d,%2d)\n",g[i].x,g[i].y); } return 0; }