题意：甲乙两条狗分别沿着一条折线奔跑，两只狗的速度未知，但已知他们同时出发，同时到达，并且都是匀速奔跑，试求甲和乙在奔跑过程中最远距离和最近距离之差。
思路：因为运动是相对的，因此也可以认为甲静止不动，乙自己沿着直线走，因此问题转化为求点到线段的最小或最大距离。然后模拟求解。大白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;
}