●UVA 11796 Dog Distance

时间：2022-06-27 16:47:08

题链：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2896

题解：

计算几何，骚操作
对于简单情况，即两只狗的路线均为一条线段，
可以从相对运动的角度出发，考虑一直狗不动，另一只狗在运动。
而由于两只狗此时都在做匀速直线运动，所以在那只不懂的狗看来，另一直狗也在匀速直线前行。（物理老师：速度的矢量和！）
所以这个简单情况下，问题就变为了求一个点到一条线段的最短和最长距离。

而本题中虽然路线为多条折线，但仍然可以根据拐点把路线拆为一个个的简单情况，进而即可求解。

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 60

using namespace std;

const double eps=1e-8;

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	void Read(){scanf("%lf%lf",&x,&y);}

};

int sign(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

typedef Point Vector;

bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}

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

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

Vector Va,Vb;

Point Da[MAXN],Db[MAXN],Pa,Pb;

int T,Na,Nb,ia,ib;

double minans,maxans,La,Lb,Lena,Lenb,tim;

double GL(Vector A){//Get_Length

	return sqrt(A*A);

}

double DTS(Point P,Point a1,Point a2){//Distance_To_Segment

	static Vector v1,v2,v3;

	v1=a2-a1; v2=P-a1; v3=P-a2;

	if(a1==a2) return GL(v2);

	if(sign(v1*v2)<0) return GL(v2);

	if(sign(v1*v3)>0) return GL(v3);

	return fabs(v2^v3)/GL(v1);

}

void contribution(Point P,Point a1,Point a2){

	minans=min(minans,DTS(P,a1,a2));

	maxans=max(maxans,GL(P-a1));

	maxans=max(maxans,GL(P-a2));

}

int main(){

	freopen("/home/noilinux/Documents/模块学习/计算几何/11796.in","r",stdin);

	scanf("%d",&T);

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

		scanf("%d%d",&Na,&Nb);

		for(int i=1;i<=Na;i++) Da[i].Read();

		for(int i=1;i<=Nb;i++) Db[i].Read();

		Lena=Lenb=0; minans=1e9; maxans=-1e9;

		for(int i=1;i<Na;i++) Lena+=GL(Da[i+1]-Da[i]);

		for(int i=1;i<Nb;i++) Lenb+=GL(Db[i+1]-Db[i]);

		ia=1,ib=1; Pa=Da[1],Pb=Db[1];

		while(ia<Na&&ib<Nb){

			La=GL(Da[ia+1]-Pa);

			Lb=GL(Db[ib+1]-Pb);

			tim=min(La/Lena,Lb/Lenb);

			Va=(Da[ia+1]-Pa)/La*tim*Lena;

			Vb=(Db[ib+1]-Pb)/Lb*tim*Lenb;

			contribution(Pa,Pb,Pb+Vb-Va);

			Pa=Pa+Va; Pb=Pb+Vb;

			if(Pa==Da[ia+1]) ia++;

			if(Pb==Db[ib+1]) ib++;

		}

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

	}

	return 0;

}

　　

相关文章