随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=2215
http://acm.hdu.edu.cn/showproblem.php?pid=2202
http://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 || (!&& 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<|| p[i].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ǎ崽 阅读(1183) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理