Surround the Trees

此题讨论区里大喊有坑，原谅我没有仔细读题还跳过了坑点。

题意：平面上有n棵树，选一些树用绳子围成一个包围圈，使得所有的树都在这个圈内。

思路：简单凸包入门题，凸包裸模板。在做这个题前建议先去学学：叉积，极角排序，三角形有向面积。

贴上代码以后再复习。

struct node

{

    double x,y;

} a[N],p[N];

int n,tot;//总点数和凸包上的点数；

double dis(node a,node b)//两点间距离

{

    return hypot(a.x-b.x,a.y-b.y);

}

//向量叉积(x1*y2-x2*y1)；为正在直线右边（逆时针排列），为负在直线左边，为0共线；

int multi(node p0,node p1,node p2)

{

    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

int cmp(node p1,node p2)

{

    int x=multi(p1,p2,a[0]);

    if(x>0||(x==0&&dis(p1,a[0])<dis(p2,a[0]))) return 1;

    return 0;

}

void Graham()

{

    int k=0;

    for(int i=1; i<n; i++) //找最下面且最靠左的点；

        if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))

            k=i;

    swap(a[0],a[k]);

    sort(a+1,a+n,cmp);//极角排序确定点的顺序；

    if(n==1)

    {

        printf("0.00\n");

        return ;

    }

    if(n==2)

    {

        printf("%.2f\n",dis(a[0],a[1]));

        return ;

    }

    tot=2,p[0]=a[0],p[1]=a[1];

    for(int i=2; i<n; i++)

    {

        while(tot>1&&multi(a[i],p[tot-1],p[tot-2])>=0) tot--;

        p[tot++]=a[i];

    }

    double diss=0;

    for(int i=0; i<tot; i++) diss+=dis(p[i],p[(i+1)%tot]);

    printf("%.2f\n",diss);

}

int main()

{

    while(~scanf("%d",&n)&&n)

    {

        for(int i=0; i<n; i++)

            scanf("%lf%lf",&a[i].x,&a[i].y);

        Graham();

    }

    return 0;

}

/*****************************************

*****************   LYQ    ***************

*****************   YES    ***************

*UserID: secrecy                         *

*RunOJ:                                  *

*RunID:                                  *

*Submit time:                            *

*Language: G++                           *

*Result: Accepted                        *

*time:                                   *

*Memory:                                 *

*Length:                                 *

*School: NYIST                           *

*Blog: http://blog.csdn.net/nyist_tc_lyq *

*QQ:                                     *

*Tel:                                    *

*****************************************/

人生第一个凸包算法，Good job!

巴特西

HDU-1392 Surround the Trees,凸包入门！

Surround the Trees

最新文章

热门文章