#include<fstream>
#include<cstdlib>
using namespace std;
ifstream fin ("bag.in");
ofstream fout ("bag.out");
struct xys
{
int x;
int y;
};
int N;//數(shù)目
xys xy[101];//坐標系
int top;//堆棧頂
int stk[101];//堆棧
void swap(xys *a,xys *b)
{
xys tmp = *a;
*a = *b;
*b =tmp;
}
int multi(xys a,xys b,xys c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);//求叉積
}
bool comp(xys p1,xys p2)
{
int t;
t=multi(p1,p2,xy[0]);
if ((t>=0)&&((p1.x-xy[0].x)+(p1.y-xy[0].y)<(p2.x-xy[0].x)+(p2.y-xy[0].y)))
return true;//叉積正確
return false;
}
void sort(int p,int r)
{
int i,j;
xys x;
if (r-p+1<=5)
{
for (j=p+1;j<=r;j++)
{
i=j;
while(i>1&&comp(xy[i],xy[i-1]))
{
swap(&xy[i],&xy[i-1]);//交換元素
i--;
}
}
}
else
{
x=xy[p+rand()%(r-p+1)];//隨即選區(qū)一個支點
i=p,j=r;
do
{
while (comp(xy[i],x))i++;
while (comp(x,xy[j]))j--;
if (i<j)swap(&xy[i],&xy[j]);
}//一次規(guī)劃
while (i<j);
sort(p,j);//前半部
sort(p+1,r);//后半部
}
}
void init()
{
int i;
fin>>N;
for(i=0;i<N;i++){
fin>>xy[i].x>>xy[i].y;
if (xy[i].y<=xy[0].y&&xy[i].x<xy[0].y) swap(xy[0],xy[i]);//交換
}
sort(1,N-1);
}
void graham()
{
int i;
for(i=1;i<=3;i++) stk[i]=i-1;
top=3;
for(i=3;i<N;i++)
{
while(multi(xy[i],xy[stk[top]],xy[stk[top-1]])>=0) top--;//所有未向左傳的點去掉
top++;
stk[top]=i;//入棧
}
for (i=1;i<=top;i++)
fout<<xy[stk[i]].x<<" "<<xy[stk[i]].y<<endl;
}
int main (void)
{
init();
graham();//掃描出凸包，打印
return 0;
}  回復  更多評論