zcmu 暑假提高（三）K - Keeping the Dogs Apart （求两个坐标的最短距离+模拟）

 K - Keeping the Dogs Apart 

Despite the unfortunate incident last summer, which resulted in ten little puppies, you have been tasked with taking care of your neighbors’ dogs again. Shadow and Lydia may be very cute mutts, but this year you have strict instructions to walk them one by one. However, you have other things to do during the summer than walking dogs! Like playing fetch and solving programming problems! It seems terribly inefficient to walk the dogs one at a time. Shadow and Lydia have a particular walk they each prefer and know by heart. If you just let them out, they will follow their favorite walk, eventually ending up in their respective doghouses. Problem solved! Sadly, you realize that if you just let both dogs out at the same time and let them do their walks on their own, they might get too close to each other. If they get too close, they will leave their favorite walk to “have some fun” and you are not sure you can find good homes for any more puppies. To ensure this does not happen, you need to calculate the minimum distance between the dogs when they are out walking on their own. Both dogs start at the same time and keep exactly the same pace. Immediately after a dog arrives at its doghouse it stays inside and goes to sleep, so we no longer need to worry about the distance to the other dog, even though the other dog may still walk for a while longer. Note that a dog is still awake at the exact moment of entering its house and falls asleep immediately after entering.

Input

For each test case: The first line of input consists of an integer$ n (2 ≤ n ≤ 100 000)$, the number of points describing the walk of Shadow. The next n lines contain 2 integers each, giving the x and y coordinates of Shadow’s walk. Two consecutive points in the walk always differ in at least one coordinate. All coordinates are non-negative and at most 10 000. Similarly, the next line contains an integer m(2 ≤ m ≤ 100000), the number of points describing the walk of Lydia. The next m lines describe its walk in the same format as for Shadow.

Output

Output the minimum distance between the two dogs during their walks. The numbers should be accurate to an absolute or relative error of at most 10−4.

Sample Input

5
10 0
10 8
2 8
2 0
10 0
9
0 8
4 8
4 12
0 12
0 8
4 8
4 12
0 12
0 8

Sample Output

1.414213562373

Hint

 

心得：数学太差，没想到用两个点距离用公式。

题意：有两只小狗，每只小狗出去散步走不同的路，问它们什么时候相聚最近，结果精确到12位小数。

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>
using namespace std;

const int INF=9999999;

struct N{
	double x,y; //建立节点
};

N p1[100100],p2[100100];
double dist(N a,N b) //求距离
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

N getn(N n1,N n2,double l) //替换节点
{
	N n3;
	double le=dist(n1,n2);
	double ex=(n2.x-n1.x)/le;
	double ey=(n2.y-n1.y)/le;
	n3.x=n1.x+ex*l;
	n3.y=n1.y+ey*l;
	return n3;
}

double getdist(N n1,N n2,N n3,N n4)  //求出最短距离
{
	double l1=dist(n1,n2);
	double l2=dist(n3,n4);
	double ex1=(n2.x-n1.x)/l1,ey1=(n2.y-n1.y)/l1;
	double ex2=(n4.x-n3.x)/l2,ey2=(n4.y-n3.y)/l2;
	
	double a=(ex1-ex2)*(ex1-ex2)+(ey1-ey2)*(ey1-ey2);
	double b=2.0*((n1.x-n3.x)*(ex1-ex2)+(n1.y-n3.y)*(ey1-ey2));
	double c=(n1.x-n3.x)*(n1.x-n3.x)+(n1.y-n3.y)*(n1.y-n3.y);
	//分类讨论二元一次方程的解
	if(a==0) return min(dist(n1,n3),dist(n2,n4));
	double t=-b/(2.0*a);
	if(t<0||t>l1) return min(dist(n1,n3),dist(n2,n4));
	return sqrt(a*t*t+b*t+c);
}

int main(void)
{
	int i,j,m,n;
	double mi;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%lf %lf",&p1[i].x,&p1[i].y);
	scanf("%d",&m);
	for(i=1;i<=m;i++) scanf("%lf %lf",&p2[i].x,&p2[i].y);
	i=2,j=2,mi=INF;
	while(i<=n&&j<=m)
	{
		double l1=dist(p1[i-1],p1[i]),l2=dist(p2[j-1],p2[j]);
		if(l1==l2) //走的边的长度相同。
		{
			mi=min(mi,getdist(p1[i-1],p1[i],p2[j-1],p2[j]));
			i++,j++;
		}
		else if(l1<l2) //l1长
		{
			N tp=getn(p2[j-1],p2[j],l1);
			mi=min(mi,getdist(p1[i-1],p1[i],p2[j-1],tp));
			i++;
			p2[j-1]=tp;
		}
		else if(l1>l2) //l2长
		{
			N tp=getn(p1[i-1],p1[i],l2);
			mi=min(mi,getdist(p1[i-1],tp,p2[j-1],p2[j]));
			j++; 
			p1[i-1]=tp;
		}
	}
	
	printf("%.12lf\n",mi); 
	return 0;
}

参考文章：https://blog.csdn.net/xbb224007/article/details/79846472