URAL 1348 Goat in the Garden 2（點到線段的距離）

URAL 1348 Goat in the Garden 2（點到線段的距離）

【題目大意】：求某點到一條線段的最小距離與最大距離。

【思路】：

分析可知，最大距離一定在端點處取得。那麼接下來求最小距離時，先求出垂線與線段所在直線的交點，然後判斷交點在不在線段上。如果在，則最小距離為垂線段的距離，即交點到此點的距離。如果不在，則最小距離必在另一端點取得。問題轉換如何判斷點與線段的垂足是否在線段上，可以利用叉積方便的求出。

代碼：

/*
* Problem: NO:URAL 1348
* Running time: 1MS
* Complier: G++
* Author: herongwei
* Create Time: 20:00 2015/10/4 星期日
*/
#include 
#include 
#include 
#include 
#include 
typedef long long LL;
using namespace std;

#define min(a,b) ab?a:b

const double eps=1e-8;
const double pi=acos(-1.0);

int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}

struct POINT //點
{
    double x,y;
    POINT(){}
    POINT(double _x ,double _y)
    {
        x = _x;
        y = _y;
    }
    POINT operator -(const POINT &b)const
    {
        return POINT(x - b.x, y - b.y);
    }
    double operator ^(const POINT &b)const
    {
        return x*b.y - y*b.x;
    }
};

struct Seg //線段
{
    POINT s,e;
    Seg(){}
    Seg(POINT _s,POINT _e)
    {
        s=_s;
        e=_e;
    }
};

struct Line//直線
{
    POINT s,e;
    Line(){}
    Line(POINT _s,POINT _e)
    {
        s=_s;
        e=_e;
    }
};

//叉乘
double cross(POINT o, POINT a, POINT b)
{
    return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}

//求兩點間的距離
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 Point_to_Line(POINT p,Line l)
{
    return fabs(cross(p,l.s,l.e)) / dis(l.s,l.e);
}

// 點到線段的距離
double Point_to_Seg(POINT p,Seg s)
{
    POINT tmp=p;
    tmp.x += s.s.y-s.e.y;
    tmp.y += s.e.x-s.s.x;
    if(cross(s.s, p, tmp) * cross(s.e, p, tmp) >= 0) /// 叉積判斷垂足是否在線段上
    {
        return min(dis(p, s.s), dis(p, s.e));
    }
    return Point_to_Line(p, Line(s.s, s.e));///垂足在線段上
}

Seg s;
POINT p;
double L;

void solve()
{
    double ans1=Point_to_Seg(p,s),ans2=max(dis(p,s.s),dis(p,s.e));
    ans1=ans1>L?ans1-L:0,ans2=ans2>L?ans2-L:0;
    printf(%.2f
%.2f
,ans1,ans2);
}

int main()
{
   while(cin>>s.s.x>>s.s.y>>s.e.x>>s.e.y)
   {
       cin>>p.x>>p.y>>L;solve();
   }
   return 0;
}

/*
input	output
8 -6 8 6
0 0 7
1.00
3.00
*/