UVA 11796- Dog Distance(计算几何_求最大距离和最小距离之差)

时间:2023-02-10 16:18:56

UVA 11796- Dog Distance(计算几何_求最大距离和最小距离之差)

题意:甲乙两条狗分别沿着一条折线奔跑,两只狗的速度未知,但已知他们同时出发,同时到达,并且都是匀速奔跑,试求甲和乙在奔跑过程中最远距离和最近距离之差。

思路:因为运动是相对的,因此也可以认为甲静止不动,乙自己沿着直线走,因此问题转化为求点到线段的最小或最大距离。然后模拟求解。大白P262


#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const double eps=1e-10;
const double pi= acos(-1.0);
struct Point {
    double x,y;
    Point(double x=0,double y=0):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 -(Point A,Point 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 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;
}
// 计算向量 A B 的点积, A*B=|A|*|B|*cosß
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));
}
// 计算叉积,AxB=|A|*|B|*sinß,得到的是与这两个向量垂直的向量
double Cross(Vector A,Vector B) {
    return A.x*B.y-A.y*B.x;
}
//三角形有向面积的两倍
double Area2(Point A,Point B,Point C) {
    return Cross(B-A,C-A);
}
//计算两点距离
double DistancePoint(Point A, Point B) {
    return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
//计算向量旋转后变成的另一个向量,rad是弧度
//公式 x1=x*cosß-y*sinß,y1=x*sinß+y*cosß;
Vector Rotate(Vector A,double rad) {
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//计算向量的单位法线, 在调用前确保 A 不是零向量
Vector Normal(Vector A) {
    double L = Length(A);
    return Vector(-A.y/L,A.x/L);
}
//直线可以用直线上一点p1,和方向向量V表示,即 向量P=点p1+V;
//计算两条直线P+tv和Q+tw的交点,调用前确保两直线有交点
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;
}
//点到直线的距离
double DistanceToLine(Point P, Point A, Point B) {
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2) / Length(v1));
}
//点到线段的距离, 有两种可能, 一种点在线段上方,这时候算垂直,不在线段上方;
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 GetLineProjectoin(Point P, Point A, Point B) {
    Vector v = B - A;
    return A + v * (Dot(v, P-A) / Dot(v, v));
}
//线段规范相交的充要条件是:每条线段的两个端点都在另一条线段的两侧(两侧指叉积的符号不同)
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 Min,Max;
Point P[60],Q[60];

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()
{
    int T,A,B,i,j;
    int icase=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&A,&B);
        for(i=0;i<A;i++)
            scanf("%lf %lf",&P[i].x,&P[i].y);
        for(i=0;i<B;i++)
            scanf("%lf %lf",&Q[i].x,&Q[i].y);
        double LenA=0,LenB=0;
        for(i=0;i<A-1;i++)
            LenA+=Length(P[i+1]-P[i]);
        for(i=0;i<B-1;i++)
            LenB+=Length(Q[i+1]-Q[i]);
        int Sa=0,Sb=0;//为刚经过的拐点的编号;
        Point Pa=P[0],Pb=Q[0];
        Min=inf,Max=-inf;
        while(Sa<A-1&&Sb<B-1){
            double La=Length(P[Sa+1]-Pa);//甲到下一个拐点的距离
            double Lb=Length(Q[Sb+1]-Pb);//乙到下一个拐点的距离
            double T=min(La/LenA,Lb/LenB);//取合适的单位,让甲乙的速度分别为LenA,LenB
            Vector va=(P[Sa+1]-Pa)/La*T*LenA;
            Vector vb=(Q[Sb+1]-Pb)/Lb*T*LenB;
            Update(Pa,Pb,Pb+vb-va);
            Pa=Pa+va;
            Pb=Pb+vb;
            if(Pa==P[Sa+1]) Sa++;
            if(Pb==Q[Sb+1]) Sb++;
        }
        printf("Case %d: %.0lf\n",icase++, Max-Min);
    }
    return 0;
}