http://acm.hdu.edu.cn/showproblem.php?pid=2215http://acm.hdu.edu.cn/showproblem.php?pid=2202http://acm.hdu.edu.cn/showproblem.php?pid=1348這三道也是基礎的凸包
模板原題：
http://acm.hdu.edu.cn/showproblem.php?pid=1392
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
struct P{
double x,y;
}p[101],stack[101];
double Mul(P p1,P p2,P p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
double dis(P a,P 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)
{
P * c = (P *)a;
P * d = (P *)b;
double k = Mul(p[0],*c,*d);
if(k<0 || (!k && dis(*c,p[0]) > dis(*d,p[0]) ) )
return 1;
return -1;
}
void tubao(int n,int &top)
{
int i;
top = 2;
stack[0] = p[0];
stack[1] = p[1];
stack[2] = p[2];
for(i=3;i<=n;i++)
{
while(Mul(stack[top-1],stack[top],p[i])<=0 && top>=2)
top --;
top ++;
stack[top] = p[i];
}
}
int main()
{
int i,top,tar,n;
double x,y;
P temp;
while(scanf("%d",&n),n)
{
tar = 0;
x = y = 0x7FFFFFFF;
for(i=0;i<n;i++)
{
scanf("%lf %lf",&p[i].x,&p[i].y);
if(p[i].x<x || p[i].x==x && p[i].y<y)
{
x = p[i].x;
y = p[i].y;
tar = i;
}
}
if(n==1)
puts("0.00");
else if(n==2)
printf("%.2lf\n",dis(p[0],p[1]));
else
{
temp = p[tar];
p[tar] = p[0];
p[0] = temp;
qsort(p+1,n-1,sizeof(p[0]),cmp);
p[n] = p[0];
tubao(n,top);
double l=0;
for(i=0;i<top;i++)
l += dis(stack[i],stack[i+1]);
printf("%.2lf\n",l);
}
}
return 0;
}
posted on 2009-03-11 13:39
shǎ崽 閱讀(1198)
評論(0) 編輯 收藏 引用