UVA 11796 - Dog Distance 向量的应用

题目大意：

甲和乙两条狗分别沿着一条折线跑，它们速度未知，但同时出发并且同时到达终点，并且都是匀速奔跑。求奔跑过程中两只狗的最大距离与最小距离之差。

思路：

因为运动是相对的，我们可以认为甲静止不动，乙沿着直线走。则问题就转化为点到线段的最小距离。

那么，我们对于每段分析，看谁先到达该线段的终点，则该段可以用上面的方法求。

把a看成不动的，则有b运动到了cb+vb-va（其中va,vb分别为a和b的位移向量，ca,cb分别为a和b初始位置）

那么就转换为sa到线段cb+vb-va的距离。（最小距离为点到直线，而最大距离一定在线段两边）

至于速度的表示，设1S到达终点，那么速度就是总长。

PS:直接用模版就是爽。哈哈

#include
  
     
#include
   
     #include
    
      using namespace std; const int MAXN=50+10; const int INF=99999999; double ans_max,ans_min; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y){ } }; typedef Point Vector; const double eps = 1e-8; int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0   -1 : 1; } Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); } Vector operator / (const Vector& A, double p) { return Vector(A.x/p, A.y/p); } bool operator == (const Point& a, const Point &b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; } double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } double Length(const Vector& A) { return sqrt(Dot(A, A)); } double DistanceToSegment(const Point& P, const Point& A, const 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); } void update(Point P,Point A,Point B) { ans_max=max(ans_max,Length(P-A));//最大的一定在端点 ans_max=max(ans_max,Length(P-B)); ans_min=min(ans_min,DistanceToSegment(P,A,B));//最小的为点到直线的距离 } Point a[MAXN],b[MAXN]; int main() { int T,kase=1; scanf(%d,&T); while(T--) { int A,B; scanf(%d%d,&A,&B); for(int i=0;i