Dog Distance

题意：两条狗匀速分别沿着折线跑，已知同时出发，同时到达，问你求相差最大的距离 与相差的最小的距离之间的差值。
题解：先看一种简单的情况：甲和乙的路线都是一条线段。因为运动是相对的，因此也可以认为甲静止不动，乙沿着自己的直线走，因此问题转化为求点到线段的最小距离和最大距离；
有了简化版的分析，只需要模拟整个过程，设现在甲的位置在Pa，刚刚经过编号为Sa的拐点；乙的位置是Pb，刚刚经过编号为Sb的拐点，则我们只需要计算他们俩谁先到拐点，那么在这个时间点之前的问题就是我们刚刚讨论过的“简化版”。求解完毕之后，需要更新甲乙的位置，如果正好到达下一个拐点，还需要更新Sa和/或Sb，然后继续模拟。因为每次至少有一条狗到达拐点，所以子问题的求解次数不会超过A+B。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<complex>
#define maxn 60
using namespace std;
double minv,maxv;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}

};
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);}
bool operator <(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
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 length(Vector A) { return sqrt(dot(A,A));}
double angle(Vector A,Vector B){return acos(dot(A,B)/length(A)/length(B)) ;}

double cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Area2(Point A,Point B,Point C){return cross(B-A,C-A);}
Vector rorate(Vector A,double rad)
{
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
Vector normal(Vector A)//左转90du，单位向量
{
    double L=length(A);
    return Vector(-A.y/L,A.x/L);
}
Point getLineIntersection(Point P,Vector v,Point Q,Vector w)//两直线的交点
{
    Vector u=P-Q;
    double t=cross(w,u)/cross(v,w);
    return P+v*t;
}
double distanceToLine(Point P,Point A,Point B)//点到直线距离
{
    Vector v1=B-A,v2=P-A;
    return fabs(cross(v1,v2))/length(v1);
}
double distanceToSegment(Point p,Point A,Point B)
{
    if(A==B) return length(p-A);
    Vector v1=B-A,v2=p-A,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 getLineProjection(Point P,Point A,Point B)//p点在AB直线上的投影
{
    Vector v=B-A;
    return A+v*(dot(v,P-A)/dot(v,v));
}
bool segmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{   //两直线是否规范相交：恰好有一个公共点并且公共点不在任何一条线段的端点
    double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1),
           c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
           return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
bool onSegment(Point p,Point a1,Point a2)//p点是否在线段上，不包括a1，a2
{
    return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;
}
double convexPolygonArea(Point *arr,int n)//计算多边形面积
{
    double area=0.0;
    for(int i=1;i<n-1;i++)
    {
        area+=cross(arr[i]-arr[0],arr[i+1]-arr[0]);
    }
    return fabs(area/2);

}
double PolygonArea(Point *arr,int n)//计算多边形有向面积
{
    double area=0.0;
    for(int i=1;i<n-1;i++)
    {
        area+=cross(arr[i]-arr[0],arr[i+1]-arr[0]);
    }
    return area/2;

}
void update(Point p,Point a,Point b)
{
    minv=min(minv,distanceToSegment(p,a,b));
    maxv=max(maxv,length(p-a));
    maxv=max(maxv,length(p-b));
}
int main()
{
   int T,n,m;
   scanf("%d",&T);
   Point p[maxn],q[maxn];
   double lena,lenb;
   for(int cas=1;cas<=T;cas++)
   {
       minv=1e9,maxv=-1e9;
       lena=0,lenb=0;
       scanf("%d%d",&n,&m);
       for(int i=0;i<n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
       for(int i=0;i<m;i++)
        scanf("%lf%lf",&q[i].x,&q[i].y);
        for(int i=0;i<n-1;i++)
        {
            lena+=length(p[i+1]-p[i]);
        }
        for(int i=0;i<m-1;i++)
        {
            lenb+=length(q[i+1]-q[i]);
        }
        Point pa=p[0],pb=q[0];
        int sa=0,sb=0;
        while(sa<n-1&&sb<m-1)
        {
            double la=length(p[sa+1]-pa),
                    lb=length(q[sb+1]-pb);
            double t=min(la/lena,lb/lenb);
            Vector va=(p[sa+1]-pa)/la*t*lena,
                    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: %.0f\n",cas,maxv-minv);

   }
}