URAL 1348 Goat in the Garden 2(点到线段的距离)

URAL 1348 Goat in the Garden 2(点到线段的距离)

http://acm.timus.ru/problem.aspx?space=1&num=1348

题意:

一只羊被绑在C点；

绳子长L米；

它发现AB直线上有凤梨；

但L有可能不够长；

求吃到一个凤梨的时候L要再拉长多少？

求吃到所有凤梨的时候L要再拉长多少？

如果L足够长则输出0；

分析:

本质就是求一个点到线段的最长最短距离.

点到线段的最短距离: 用刘汝佳<<训练指南>>的模板. 大体思想是判断点的投影是否在线段上,如果点的投影在线段上,那么最短距离就是点到线段的垂线段. 否则最短距离就是点到线段两个端点距离的最小者.

点到线段的最长距离: 一定是点到线段两端点最长距离的最大值.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
bool operator==(Point A,Point B)
{
    return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0;
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Length(Vector A)
{
    return sqrt(Dot(A,A));
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double DistanceToSegment(Point P,Point A,Point B)//P点到线段AB最短距离
{
    if(A==B) return Length(P-A);
    Vector v1=P-A,v2=P-B,v3=B-A;
    if(Dot(v1,v3)<0) return Length(v1);
    else if(Dot(v2,v3)>0) return Length(v2);
    else return fabs(Cross(P-A,P-B))/Length(A-B);
}

int main()
{
    Point A,B,C;
    double L;
    scanf("%lf%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&L);
    double max_len,min_len;
    min_len = DistanceToSegment(C,A,B);
    max_len = max(Length(C-A), Length(C-B));
    printf("%.2lf\n%.2lf\n",min_len>L?min_len-L:0, max_len>L?max_len-L:0);
    return 0;
}