UVa 11796 计算几何

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2896

大概思路：A和B运动，以A（Posa）为参考点，求出B的运动轨迹（Posb -> Posb + Vb-Va）;

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn = ;

const int maxe = ;

const int INF = 0x3f3f3f;

const double eps = 1e-;

const double PI = acos(-1.0);

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);

}

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

///求点P到线段AB的距离，先看Q点在线段外还是内；利用点积就可以，

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 read_point(){

    Point A;

    scanf("%lf %lf",&A.x,&A.y);

    return A;

}

double Min, Max;

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()

{

    ///freopen("E:\\acm\\input.txt","r",stdin);

    ///freopen("E:\\acm\\output.txt","w",stdout);

    int T,a,b;

    Point A[maxn],B[maxn];

    cin>>T;

    for(int t=;t<=T;t++){

        cin>>a>>b;

        for(int i=;i<=a;i++)  A[i] = read_point();

        for(int i=;i<=b;i++)  B[i] = read_point();

        double lenA = ,lenB = ;

        for(int i=;i<a;i++)   lenA += Length(A[i+]-A[i]);

        for(int i=;i<b;i++)   lenB += Length(B[i+]-B[i]);  //这儿也能写错；复制就是不好。

        int Sa = , Sb = ;

        Point Posa = A[], Posb = B[];  // 现在甲乙所在的位置；

        Min =  1e9, Max = -1e9;

        while(Sa < a && Sb < b){

            double  La = Length(A[Sa+]-Posa);

            double  Lb = Length(B[Sb+]-Posb);

            double  T = min(La/lenA,Lb/lenB);  // 取合适的单位，可以让甲和乙的速度分别是LenA和LenB

            Vector  Va = (A[Sa+]-Posa)/La * T * lenA;  //A在这次比较下的位移向量；

            Vector  Vb = (B[Sb+]-Posb)/Lb * T * lenB;

            update(Posa,Posb,Posb+Vb-Va);  //Vb-Va是A在相对静止时，B的位移向量；

            Posa = Posa + Va;

            Posb = Posb + Vb;

            if(Posa == A[Sa+])  Sa++;

            if(Posb == B[Sb+])  Sb++;

        }

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

    }

    return ;

}