uva 11798 相对运动的最小最大距离

Two dogs, Ranga and Banga, are running randomly following two different paths. They both run for T seconds with different speeds. Ranga runs with a constant speed of R m/s, whereas Banga runs with a constant speed of S m/s. Both the dogs start and stop at the same time. Let D(t) be the distance between the two dogs at time t.

The dog distance is equal to the difference between the maximum and the minimum distance between the two dogs in their whole journey.

Mathematically,

Dog Distance = {max (D(a)) 0 <= a <= T} – {min (D(b))  0 <= b <= T}

Given the paths of the two dogs, your job is to find the dog distance.

Each path will be represented using N points, (P₁ P₂ P₃ … P_N). The dog following this path will start from P₁ and follow the line joining with P₂, and then it will follow the line joining P₂-P₃, thenP₃-P₄ and so on until it reaches P_n.

Input

Input starts with an integer I(I≤1000), the number of test cases.

Each test case starts with 2 positive integers A(2≤A≤50), B(2≤B≤50). The next line contains the coordinates of A points with the format X₁ Y₁ X₂ Y₂ …X_A Y_A, (0≤ X_i,Y_i ≤1000). These points indicate the path taken by Ranga. The next line contains B points in the same format. These points indicate the path taken by Banga. All distance units are given in meters and consecutive points are distinct. All the given coordinates are integers.

Note that the values of T, R and S are unknown to us.

Output

For each case, output the case number first. Then output the dog distance rounded to the nearest integer. Look at the samples for exact format.

题目大意：两条狗按各自的折线线路奔跑，它们同时出发同事到达终点。求奔跑过程中两只狗的最大距离与最小距离之差。

标记为红色的均为向量，其他的则为点。

分析：整个过程可以按折点细化成多个它们沿着各自的线段奔跑同时出发同时到达终点，假设它们的起点为sa,sb终点为ea,eb，位移为Sa,Sb。运动是相对的所以可以认为一只狗不动待在sa，另一只口沿着直线跑。以a为参考系，b相对a的速度为Vb–Va。由于它们的运动时间相等s=vt,所以这个过程等同与b从sb移动到（sb+(Sb–Sa)),即转化为求点sa到线段（sb — sb+(Sb-Sa)）的最大距离与最小距离。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;struct Point
{
    double x,y;
    Point(double x=,double y=):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-;
int dcmp(double x)
{
    if(fabs(x)<eps) return ;
    else return x<?-:;
}
bool operator == (const Point &a,const Point &b){
    return (dcmp(a.x-b.x)== && dcmp(a.y-b.y)==);
}
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;}Vector Rotate(Vector A,double rad)//向量旋转
{
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}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)) < ) return Length(v2);
    else if(dcmp(Dot(v1,v3)) > ) return Length(v3);
    else return fabs(Cross(v1,v2))/Length(v1);
}Point GetLineProjection(Point P,Point A,Point B)//P在直线上的投影点
{
    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)< && dcmp(c3)*dcmp(c4)<;
}bool OnSegment(Point p,Point a1,Point a2)//点是否在线段上
{
    return dcmp(Cross(a1-p,a2-p))== && dcmp(Dot(a1-p,a2-p))<;
}double PolygonArea(Point *p,int n)//多边形的有向面积
{
    double area=;
    for(int i=;i<n-;i++)
        area+=Cross(p[i]-p[],p[i+]-p[]);
    return area/;
}const int maxn=;
int T,A,B,Icase;
Point P[maxn],Q[maxn];
double Min,Max;
double LenA,LenB,La,Lb,t;
int i,sa,sb;
Point Pa,Pb;
Vector Va,Vb;Point read_point()
{
    Point p;
    scanf("%lf %lf",&p.x,&p.y);
    return p;
}double min(double a,double b)
{
    if(a-b>0.00000001) return b;
    else return a;
}double max(double a,double b)
{
    if(a-b>0.00000001) return a;
    else return b;
}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));
    //printf("%.lf %.lf %.lf %.lf %.lf %.lf\n",P.x,P.y,A.x,A.y,B.x,B.y);
}int main()
{
    Icase=;
    scanf("%d",&T);
    while(T--)
    {
        Icase++;
        Min=1e9,Max=-1e9;
        //printf("%.lf %.lf\n",Min,Max);
        scanf("%d %d",&A,&B);
        for(i=;i<A;i++) P[i]=read_point();
        for(i=;i<B;i++) Q[i]=read_point();
        LenA=LenB=;
        for(i=;i<A;i++) LenA+=Length(P[i]-P[i-]);
        for(i=;i<B;i++) LenB+=Length(Q[i]-Q[i-]);
        sa=sb=;
        Pa=P[],Pb=Q[];
        while(sa<A- && sb<B-)
        {
            La=Length(P[sa+]-Pa);
            Lb=Length(Q[sb+]-Pb);
            t=min(La/LenA,Lb/LenB);
            Va=(P[sa+]-Pa)/La*t*LenA;
            Vb=(Q[sb+]-Pb)/Lb*t*LenB;
            update(Pa,Pb,Pb+Vb-Va);
            Pa=Pa+Va;
            Pb=Pb+Vb;
            if(Pa==P[sa+]) sa++;
            if(Pb==Q[sb+]) sb++;
        }
        //printf("%lf %lf\n",Max,Min);
        printf("Case %d: %.0lf\n",Icase,Max-Min);
    }
    return ;
}