Goat in the Garden 2（点到线段的最短距离）

绝地灬酷狼 2023-10-11 12:52 48阅读 0赞

> 题目衔接：[http://acm.timus.ru/problem.aspx?space=1&num=1348][http_acm.timus.ru_problem.aspx_space_1_num_1348]

>  
> 
> A goat is tied to a peg (in a point *C*) in a garden with a strong rope of the length *L* (i.e. a goat may eat a grass that is not farther than *L* meters from the peg). There is a bed of pineapples that he loves very much. The bed is a line segment with the ends *A* and *B*.
> 
> Humph… We wonder, how much the goat is to stretch the roap in order to reach at least one pine apple? And all the pineapples?
> 
> ### Input ###
> 
> There are points’ A, B and C coordinates and a length of the rope *L* in the input. All the numbers are integer, *L* ≥ 0, all the coordinates don’t exceed 10000 by the absolute value. The numbers are separated with spaces or line feeds.
> 
> ### Output ###
> 
> The first line should contain the minimal length that the goat is to elongate the rope in order to reach the pineapples bed. The second line should contain the minimal length that the goat is to elongate the rope in order to eat all the pineapples from the bed. All the numbers are to be outputted within two digits after a decimal point.

>  
> 
> ### Sample ###
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <th>input</th> 
>    <th>output</th> 
>   </tr> 
>   <tr> 
>    <td> <pre>8 -6 8 6
> 0 0 7
> </pre> </td> 
>    <td> <pre>1.00
> 3.00
> </pre> </td> 
>   </tr> 
>  </tbody> 
> </table>

> 题目大意：一只山羊被栓在柱子上，有一个长床，上面有很多好吃的，现在羊要吃床上的东西  
> 问你这个羊吃到一个需要拉伸多长的绳子，吃到所有的需要拉伸多长
> 
> 思路:  
> 以山羊所在地方为圆，则吃到一个即为山羊到这条线段的最短距离，最远则是山羊到两个端点取最大值

/*
    题目大意：一只山羊被栓在柱子上，有一个长床，上面有很多好吃的，现在羊要吃床上的东西
    问你这个羊吃到一个需要拉伸多长的绳子，吃到所有的需要拉伸多长
    
    思路:
    以山羊所在地方为圆，则吃到一个即为山羊到这条线段的最短距离，最远则是山羊到两个端点取最大值
    */
    #include<set>
    #include<map>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    #define inf 0x3f3f3f
    #define bug  printf("bug\n")
    const int maxn=1e6+10;
    const double pi=acos(-1.0);
    const double esp=1e-6;
    const int N=2e2+10;
    struct point
    {
        double x,y;
    };
    struct line
    {
        point st,ed;
        double k,b;
    };
    int sign(double x)
    {
        if(fabs(x)<esp)
            return 0;
        return x>0?1:-1;
    }
    double getk(line l)
    {
        if(l.st.x==l.ed.x)///斜率不存在
            return inf;
        return (l.ed.y-l.st.y)/(l.ed.x-l.st.x);
    }
    double getb(line l)
    {
        return l.ed.y-l.k*l.ed.x;
    }
    double dis(point a,point b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    double cmult(point a,point b,point c)///叉积
    {
        return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
    }
    double pmult(point a,point b)///点积 这里的ab表示的是向量
    {
        return a.x*b.x+a.y*b.y;
    }
    ///如何判断点是否在线段上且距离线段的最短距离是多少
    double pldis(point a,line l)
    {
        point s1,s2,s3;
        s1.x=l.ed.x-l.st.x,s1.y=l.ed.y-l.st.y;
        s2.x=a.x-l.st.x,s2.y=a.y-l.st.y;
        s3.x=a.x-l.ed.x,s3.y=a.y-l.ed.y;
        if(l.st.x==l.ed.x&&l.st.y==l.ed.y)
            return dis(a,l.st);
        if(sign(pmult(s1,s2))<0)///两向量成钝角
            return dis(a,l.st);
        else if(sign(pmult(s1,s3))>0)
            return dis(a,l.ed);
        else///该处为c在线段上方
            return fabs(cmult(l.st,a,l.ed))/dis(l.st,l.ed);
    }
    int main()
    {
        line l;
        point a;
        double r;
        while(scanf("%lf%lf%lf%lf%lf%lf%lf",&l.st.x,&l.st.y,&l.ed.x,&l.ed.y,&a.x,&a.y,&r)!=EOF)
        {
            double minx=pldis(a,l);
            minx=minx>r?minx-r:0;
            double maxx=max(dis(a,l.st),dis(a,l.ed));
            maxx=maxx>r?maxx-r:0;
            printf("%.2lf\n%.2lf\n",minx,maxx);
        }
        return 0;
    }

[http_acm.timus.ru_problem.aspx_space_1_num_1348]: http://acm.timus.ru/problem.aspx?space=1&num=1348