HDU 1392 Surround the Trees(凸包模板)

http://acm.hdu.edu.cn/showproblem.php?pid=1392

这题是凸包的模板题目……看算法后纯原创+_+

思路：

1：在输入的时候就保留住最下面而又靠左的点，这点为起点p0；设置hash表为是否访问过该点，因为结束标志是找到下一个顶点为p0,所以初始化时不可以将p0点赋为已经访问

做n个循环，pi保留下一个要开始求凸包边的点

2：循环从P0开始，设置点Pj也是p0，然后

3：将j从0开始，找到所以的未访问的点，依次和pi,pj进行叉乘，(j-pi)×(pj-pi)，大于0时j在pj顺时针方向，小于0就在逆时针方向。等于0时则共线，返回距离较远的那个点，结果保留在pj里面。

4：所有点测试完则把更新好了的pj放在pi里，这是下一个凸包的顶点；并记录至今为止的总距离

5：如果pi已经是p0了，就可以输出了，否则在从2继续。

这题里的n=1,n=2,以及共线，都是特殊情况，要注意

#include<stdio.h>
#include<math.h>
struct node
{
  double x,y;
}p[110];
int hash[110],flag;
double distance(int a,int b)//求两点之间距离
{
    return sqrt(pow(p[a].x-p[b].x,2)+pow(p[a].y-p[b].y,2));
}
int cross_product(int a,int b,int c)//求两向量叉乘
{
    double x1,y1,x2,y2;
    x1=p[a].x-p[c].x;
    y1=p[a].y-p[c].y;
    x2=p[b].x-p[c].x;
    y2=p[b].y-p[c].y;
    if(x1*y2-x2*y1>0)
     {
        flag=1;
        return a;
     }
    else if(fabs(x1*y2-x2*y1)<1e-6)
    {
        if(distance(a,c)>distance(b,c))return a;
        else return b;
    }
    return b;
}
int main()
{
    int n,i,p0,j,pj,pi;
    double x0,y0,sum;
    while(scanf("%d",&n),n)
    {
        sum=0;
        flag=0;
        x0=y0=999999;
        for(i=0;i<n;i++)
        {
            hash[i]=0;
            scanf("%lf%lf",&p[i].x,&p[i].y);
            if(p[i].y<y0||(p[i].y==y0&&p[i].x<x0))
            {
                x0=p[i].x;
                y0=p[i].y;
                p0=i;
            }
        }
        if(n==1)
        {
            printf("0.00
");
            continue;
        }
        if(n==2)
        {
            printf("%.2lf
",distance(0,1));
            continue;
        }
            pi=p0;
        for(i=0;i<n;i++)
        {
            pj=p0;
            //while(pj==p0||(pj<n&&hash[pj]))pj++;
            for(j=0;j<n;j++)
            {
                  pj=cross_product(j,pj,pi);
            }
            hash[pj]=1;
            sum=sum+distance(pi,pj);
            pi=pj;
            if(pj==p0)break;
        }
        if(flag)
        printf("%.2lf
",sum);
        else printf("%.2lf
",sum/2);
    }
    return 0;
}

View Code

HDU 1392 Surround the Trees(凸包模板)

相关推荐