第一次寫凸包，最簡單的那種……。
  code
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
typedef struct
{
int x,y;
}Point;
Point p[55];
Point ans[55];
Point start;
int CMP(Point a,Point b,Point c)//ab叉乘ac
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double Distance(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int cmp(const void *a,const void *b)
{
Point *p1,*p2;
p1=(Point *)a;
p2=(Point *)b;
if(CMP(start,*p1,*p2)<0)
return 1;
/*else if(CMP(start,*p1,*p2)==0&&Distance(start,*p1)<Distance(start,*p2))
{
return 1;
}*/
else return -1;
}
int Find_start(int n)
{
int i;
start.y=10000;
start.x=10000;
for(i=1;i<=n;i++)
{
if(ans[i].y<start.y)
{
start.x=ans[i].x;
start.y=ans[i].y;
}
else if(ans[i].y==start.y&&ans[i].x<start.x)
{
start.x=ans[i].x;
start.y=ans[i].y;
}
}
int t=0;
for(i=1;i<=n;i++)
{
if(ans[i].x==start.x&&ans[i].y==start.y)
continue;
else
{
p[++t].x=ans[i].x;
p[t].y=ans[i].y;
}
}
p[0].x=start.x;
p[0].y=start.y;
return 0;
}
int top=2;
int tubao(int n)
{
ans[0].x=start.x;
ans[0].y=start.y;
ans[1].x=p[1].x;
ans[1].y=p[1].y;
ans[2].x=p[2].x;
ans[2].y=p[2].y;
int i;
for(i=3;i<n;i++)
{
while(CMP(ans[top-1],ans[top],p[i])<=0)
top--;
ans[++top].x=p[i].x;
ans[top].y=p[i].y;
}
return 0;
}
int main()
{
int x,y;
int i=0;
int n,j;
while(scanf("%d",&x)!=EOF)
{
scanf("%d",&y);
ans[++i].x=x;
ans[i].y=y;
}
n=i;
Find_start(n);
qsort(&p[1],n-1,sizeof(p[1]),cmp);
tubao(n);
for(i=0;i<=top;i++)
{
if(ans[i].x==0&&ans[i].y==0)
{
j=i;
break;
}
}
for(i=j;i<=top;i++)
{
printf("(%d,%d)\n",ans[i].x,ans[i].y);
}
for(i=0;i<j;i++)
{
printf("(%d,%d)\n",ans[i].x,ans[i].y);
}
return 0;
}
|