相对运动模拟：UVa 11796 Dog Distance

参考《算法竞赛入门经典——训练指南》第四章 计算几何

参考代码+部分注释

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <climits>
#define eps 1e-10
using namespace std;
typedef long long ll;
const int INF=INT_MAX;
const int maxn = 50+10;
int dcmp(double x){//三态函数，克服浮点数精度陷阱，判断x==0?x<0?x>0?
  if(fabs(x)<eps) return 0;else return x<0?-1:1;
}
struct Point{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}//构造函数，方便代码编写
};
typedef Point Vector;//Vector是 Point的别名

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);}
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;}
//向量旋转，rad是弧度不是角度
Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
//直线交点，调用前请确保两条直线P+tv,Q+tw有唯一交点。当且仅当Cross（v,w）非0
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;
}
//线段规范相交判定
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){
 return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
}
//返回点到线段的距离
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 P[maxn],Q[maxn];
int A,B;
double Max,Min;

void update(Point P,Point A,Point B){
  Min=min(Min,DistanceToSegment(P,A,B));//最小值Min在点到线段的距离取得
  Max=max(max(Max,Length(P-A)),Length(P-B));
}

int main()
{
 //  freopen("input.txt","r",stdin);
   int kase=0;
   int T;cin>>T;
   while(T--){
    cin>>A>>B;
    for(int i=0;i<A;i++) cin>>P[i].x>>P[i].y;
    for(int j=0;j<B;j++) cin>>Q[j].x>>Q[j].y;
    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;//Sa,Sb记录当前经过的编号
    Max=-1e9,Min=1e9;
    Point Pa=P[0],Pb=Q[0];//Pa,Pb记录经过的位置（Pa、Pb是点,在模拟过程作累加变量，区别Sa、Sb）
   
    while(Sa<A-1&&Sb<B-1){//后面的模拟过程都假设a,b的速度为LenA、LenB
     double La=Length(P[Sa+1]-Pa);//La表示甲到下一个拐点的距离
     double Lb=Length(Q[Sb+1]-Pb);//Lb表示乙到下一个拐点的距离
     double time=min(La/LenA,Lb/LenB);//取时间的最小值，在该段时间内，有人到达，有人未到达
     Vector Disa=(P[Sa+1]-Pa)/La*(time*LenA);//在这段时间内的位移量取决于总位移向量×运动的距离time*LenA占总距离La的比例
     Vector Disb=(Q[Sb+1]-Pb)/Lb*(time*LenB);//在这段时间内的位移量取决于总位移向量×运动的距离time*LenA占总距离La的比例
     update(Pa,Pb,Pb+(Disb-Disa));//更新最大值和最小值，注意相对运动的表示(位移向量的差)
     Pa=Pa+Disa;//位移量累加
     Pb=Pb+Disb;
     if(Pa==P[Sa+1]) Sa++;//到达下一结点就更新当前的编号
     if(Pb==Q[Sb+1]) Sb++;
    }
    
    printf("Case %d: %.0f\n",++kase,Max-Min);
   }
   return 0;
}