简单几何(相对运动距离最值) UVA 11796 Dog Distance

 

题目传送门

题意：两只狗在折线上跑，速度未知，同时出发，同时达到。问跑的过程中，两狗的最大距离和最小距离的差

分析：训练指南P261，考虑相对运动，设A静止不动，B相对A运动，相对的运动向量：Vb - Va(可以理解为速度矢量)，那么就是pa到线段pb-pb+Vb-Va的距离最值

 

/************************************************
* Author        :Running_Time
* Created Time  :2015/10/22 星期四 10:21:19
* File Name     :UVA_11796.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 55 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
struct Point    {
    double x, y;
    Point (double x=0, double y=0) : x (x), y (y) {}
};
typedef Point Vector;
double dot(Vector A, Vector B)  {
    return A.x * B.x + A.y * B.y;
}
double cross(Vector A, Vector B)    {
    return A.x * B.y - A.y * B.x;
}
int dcmp(double x)  {
    if (fabs (x) < EPS) return 0;
    else    return x < 0 ? -1 : 1;
}
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 length(Vector A) {
    return sqrt (dot (A, A));
}
double dis_to_seg(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 A[N], B[N];
double mx, mn;

void updata(Point p, Point a, Point b)  {
    mn = min (mn, dis_to_seg (p, a, b));
    mx = max (mx, max (length (p - a), length (p - b)));
}

int main(void)    {
    int T, cas = 0; scanf ("%d", &T);
    while (T--) {
        int na, nb;   scanf ("%d%d", &na, &nb);
        for (int i=0; i<na; ++i)    scanf ("%lf%lf", &A[i].x, &A[i].y);
        for (int i=0; i<nb; ++i)    scanf ("%lf%lf", &B[i].x, &B[i].y);
        double lena = 0, lenb = 0;
        for (int i=0; i<na-1; ++i)  lena += length (A[i+1] - A[i]);
        for (int i=0; i<nb-1; ++i)  lenb += length (B[i+1] - B[i]);
        int sa = 0, sb = 0;
        mx = -1e9;   mn = 1e9;
        Point pa = A[0], pb = B[0];
        while (sa < na - 1 && sb < nb - 1)  {
            double la = length (A[sa+1] - pa);
            double lb = length (B[sb+1] - pb);
            double tim = min (la / lena, lb / lenb);
            Vector Va = (A[sa+1] - pa) / la * tim * lena;
            Vector Vb = (B[sb+1] - pb) / lb * tim * lenb;
            updata (pa, pb, pb + Vb - Va);
            pa = pa + Va;
            pb = pb + Vb;
            if (pa == A[sa+1])  sa++;
            if (pb == B[sb+1])  sb++;
        }
        printf ("Case %d: %.0f\n", ++cas, mx - mn);
    }

    return 0;
}