《训练指南》—

《训练指南》——8.5

Uva 11796：

甲和乙两条狗分别沿着一条折线奔跑。两只狗的速度位置，但已知他们同时出发，同时到达，并且都是匀速奔跑。你的任务是求出甲和乙在奔跑过程中的最远距离和最近距离之差。

分析：这里分析两只狗在运动过程的距离问题，我们这里面临如下两个困难：

(1) 两只狗都在动。

(2) 狗的运动路线是折线。

为了解决第一个问题，我们这里考虑物理当中的运动相对性，我们假设两只狗当前走得都是直线(简化模型)，我们将一直狗视为静止，做其运动方向所在向量的相反向量，将其和另一只狗的运动向量进行合成，那么合成后的向量路径其实就能够准确的表示两只狗的相对位置，那么我们求解比较困难的两个动点间距离的最大值最小值的问题就转化成了顶点到确定线段距离的最大值或者最小值。

而针对第二个问题，我们只需要在模拟计算的过程中，将整个运动过程一一划分成上文所给出的“简化模型”即可。

那么现在我们要在代码层面进行更为详细的讨论：

如何求解一个顶点到一条线段的最短距离(最长距离)呢？

最长距离很好理解，一定是这个顶点到线段的两个端点连线的其中一个，这个就不必赘言，这里我们主要分析一下最短距离。

首先我们要将几何中所有的情况罗列出来，这样对应着我们才能够进行代码实现。

下面基于图形我们进行简单的代数运算。

需要注意的几点是，这里的情况其实包含了P在A、B上的情况。从微积分的教材上，向量的叉乘得到的是向量，但是这里我们进行叉乘运算得到的是数字，因此上式叉乘外边的“||”符号是绝对值的意思。

简单的参考代码如下(未提交)：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
const double eps=1e-10;


using namespace std;


struct Point
{
    double x;
    double y;
    Point(double x=0,double y=0):x(x),y(y){}
    void operator<<(Point &A) {cout<<A.x<<' '<<A.y<<endl;}
};

int dcmp(double x)  {return (x>eps)-(x<-eps); }

typedef  Point  Vector;

Vector  operator +(Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y);}

Vector  operator -(Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }

Vector  operator *(Vector A,double p) { return Vector(A.x*p,A.y*p);  }

Vector  operator /(Vector A,double p) {return Vector(A.x/p,A.y/p);}

// ps  cout

ostream &operator<<(ostream & out,Point & P) { out<<P.x<<' '<<P.y<<endl; return out;}

bool  operator< (const Point &A,const Point &B) { return A.x<B.x||(A.x==B.x&&A.y<B.y); }

bool  operator== ( const Point &A,const 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  Cross(Vector A,Vector B)  {return A.x*B.y-B.x*A.y; }

double  Length(Vector A)  { return sqrt(Dot(A, A));}

double DistanceToSegment(Point P , Point A , Point B)
{
    if(A == B)  return Length(P-A);
    Vector v1 = B-A ;
    Vector v2 = P-A ;
    Vector v3 = P-B ;
    if(dcmp(Dot(v1,v2)) < 0)  return Length(v2);
    else if(dcmp(Dot(v1,v3)) > 0) return Length(v3);
    else return fabs(Cross(v1 , v2))/Length(v1);
}

Point  read_point()
{
    Point P;
    scanf("%lf%lf",&P.x,&P.y);
    return  P;
}

double Max,Min;

const int maxn=60;

Point P[maxn],Q[maxn];

void update(Point P,Point A,Point B)
{
    Min=min(Min,DistanceToSegment(P, A,B));

    Max=max(Max,Length(P-A));
    Max=max(Max,Length(P-B));

}


int main()
{
    int T;
    int A,B;
    cin>>T;
    for(int kase = 1;kase <= T;kase++)
    {
        cin>>A>>B;

        for(int i=0;i<A;i++)  P[i]=read_point();
        for(int i=0;i<B;i++)  Q[i]=read_point();

        double LenA=0,LenB=0;

        for(int i=0;i<A-1;i++)  LenA+=Length(P[i+1]-P[i]);
        for(int i=0;i<B-1;i++)  LenB+=Length(Q[i+1]-Q[i]);

        int Sa=0,Sb=0;
        Min= 1e9;
        Max=-1e9;

        Point Pa=P[0];
        Point Pb=Q[0];

          while(Sa<A-1 && Sb < B-1)
         {
             double  La=Length(P[Sa+1]-Pa);
             double  Lb=Length(Q[Sb+1]-Pb);

             double T=min(La/LenA,Lb/LenB);

             Vector Va=(P[Sa+1]-Pa)/La*T*LenA;
             Vector Vb=(Q[Sb+1]-Pb)/Lb*T*LenB;

             update(Pa,Pb,Pb+Vb-Va);

             Pa=Pa+Va;
             Pb=Pb+Vb;

             if(Pa==P[Sa+1])  Sa++;
             if(Pb==Q[Sb+1])  Sb++;
         }




        printf("Case %d: %.0lf
",kase,Max -Min);

    }


}