uva 11796 Dog Distance （计算几何-点和直线）

 

C	Dog Distance
	Input	Standard Input
	Output	Standard Output

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₃, then P₃-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.

 

 

Sample Input	Sample Output
2 2 2 0 0 10 0 0 1 10 1 3 2 635 187 241 269 308 254 117 663 760 413	Case 1: 0 Case 2: 404

 

 题目大意：

两条狗匀速分别沿着折线跑，已知同时出发，同时到达，问你求相差最大的距离 与相差的最小的距离之间的差值。

解题思路：

如果两只狗都走1条线段的话，根据相对运动的理论，可以把其中一只狗看成静止不动，另一只狗相对运动，且线路为线段，那么立刻转化为点到线段的距离的问题。

解题代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps=1e-7;
struct Point{
    double x,y;
    Point(double x0=0,double y0=0){
        x=x0,y=y0;
    }
    friend bool operator < (Point a,Point b){
        if(a.y!=b.y) return a.y<b.y;
        else return a.x<b.x;
    }
};

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); }
int dcmp(double x) { if(fabs(x)<eps) return 0; else 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; }
Vector Rotate(Vector A,double rad){ return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); }//逆时针旋转rad弧度
double torad(double ang){ return ang/180.0*acos(-1.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);
}

const int maxn=1100;
Point p[maxn],q[maxn];
int na,nb;
double minans,maxans;

void input(){
    minans=1e9,maxans=-1e-9;
    scanf("%d%d",&na,&nb);
    for(int i=0;i<na;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=0;i<nb;i++) scanf("%lf%lf",&q[i].x,&q[i].y);
}

void update(Point x,Point a,Point b){
    minans=min(minans,DistanceToSegment(x,a,b));
    maxans=max(maxans,Length(x-a));
    maxans=max(maxans,Length(x-b));
}

void solve(){
    double lena=0,lenb=0;
    for(int i=1;i<na;i++) lena+=Length(p[i]-p[i-1]);
    for(int i=1;i<nb;i++) lenb+=Length(q[i]-q[i-1]);

    int la=0,lb=0;
    Point pa=p[0],pb=q[0];
    while(la<na-1 && lb<nb-1){
        double disa=Length(p[la+1]-pa);
        double disb=Length(q[lb+1]-pb);
        double t0=min(disa/lena,disb/lenb);
        Vector offa=(p[la+1]-pa)/disa*t0*lena;
        Vector offb=(q[lb+1]-pb)/disb*t0*lenb;
        update(pa,pb,pb+offb-offa);
        pa=pa+offa;
        pb=pb+offb;
        if(pa==p[la+1]) la++;
        if(pb==q[lb+1]) lb++;
    }
    printf("%.0lf\n",maxans-minans);
}

int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        input();
        printf("Case %d: ",i);
        solve();
    }
    return 0;
}