HDU-1392-Surround the Trees

r囧r小猫 2022-02-16 18:36 153阅读 0赞

题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=1392][http_acm.hdu.edu.cn_showproblem.php_pid_1392]

> # Surround the Trees #
> 
> **Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
> Total Submission(s): 14038    Accepted Submission(s): 5428**  
>   
>  
> 
> **Problem Description**
> 
> There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?   
> The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.
> 
> ![1392-1.gif][]
> 
>   
>   
> There are no more than 100 trees.
> 
>  
> 
>  
> 
> **Input**
> 
> The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.  
>   
> Zero at line for number of trees terminates the input for your program.
> 
>  
> 
>  
> 
> **Output**
> 
> The minimal length of the rope. The precision should be 10^-2.

>  样例输入输出：
> 
>      
> 
> 9 12 7 24 9 30 5 41 9 80 7 50 87 22 9 45 1 50 7 0
> 
> 243.06

题目大意:给你一个树林，问你最短需要多长的绳子能把整个树林包起来

思路：看一下图就感觉是凸包，我们可以使用Graham算法，扫描后计算长度（凸包试水）

注意两点：一：当只有一个点或两个点的时候要特判

二：算的时候不要忘记算最后一个点与第一个点的距离

代码：

/*
    题目大意:给你一个树林，问你最短需要多长的绳子能把整个树林包起来
    
    思路：看一下图就感觉是凸包，我们可以使用Graham算法，扫描计算长度（凸包试水）
    
    */
    #include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include <vector>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    #define Test() {freopen("F:\\test.in","r",stdin);freopen("F:\\test1.out","w",stdout);}
    const int maxn=2e4+10;
    const double pi=acos(-1.0);
    const int N=110;
    const ll mod=1e9+7;
    struct point
    {
        int x,y;
    } p[maxn];
    int Stack[maxn],top;
    int sign(double x)
    {
        if(fabs(x)<esp)
            return 0;
        if(x<0)
            return -1;
        else
            return 1;
    }
    ///距离
    double dis(point a,point b)
    {
        return sqrt((double)pow((a.x-b.x),2)+pow((a.y-b.y),2));
    }
    ///叉积
    int mulit(point a,point b,point c)
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    ///极角排序：按照该点与x轴的夹角进行逆时针比较
    bool cmp(point a,point b)
    {
        int temp=mulit(p[0],a,b);
        if(temp>0)
            return true;
        if(temp==0&&dis(p[0],a)<dis(p[0],b))
            return true;
        return false;
    }
    ///凸包
    void tb(int n)
    {
        point p0;
        int k;
        p0=p[0];
        for(int i=1; i<n; i++)
        {
            if(p0.y>p[i].y||(p0.y==p[i].y&&p0.x>p[i].x))
            {
                p0=p[i];
                k=i;
            }
        }
        p[k]=p[0];
        p[0]=p0;
        sort(p+1,p+n,cmp);
        if(n==1)
        {
            top=0;
            Stack[0]=0;
            return ;
        }
        if(n==2)
        {
            top=1;
            Stack[0]=0;
            Stack[1]=1;
            return ;
        }
        if(n>2)
        {
            for(int i=0; i<=1; i++)
                Stack[i]=i;
            top=1;
            for(int i=2; i<n; i++)
            {
                while(top>0&&mulit(p[Stack[top-1]],p[Stack[top]],p[i])<=0)
                    top--;
                top++;
                Stack[top]=i;
            }
        }
    }
    
    
    int main()
    {
        int n;
        while(scanf("%d",&n)&&n)
        {
            for(int i=0; i<n; i++)
                cin>>p[i].x>>p[i].y;
            if(n==1)
            {
                printf("0.00\n");
                continue;
            }
            if(n==2)
            {
                printf("%.2lf\n",dis(p[0],p[1]));
                continue;
            }
            tb(n);
            double ans=0;
            for(int i=0; i<top; i++)
                ans+=dis(p[Stack[i]],p[Stack[i+1]]);
            ans+=dis(p[Stack[0]],p[Stack[top]]);
            printf("%.2lf\n",ans);
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1392]: http://acm.hdu.edu.cn/showproblem.php?pid=1392
[1392-1.gif]: http://acm.hdu.edu.cn/data/images/1392-1.gif