K - Keeping the Dogs Apart GYM-101550（计算几何）

本文主要是介绍K - Keeping the Dogs Apart GYM-101550（计算几何），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

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

题意：
给出两只狗的路线，且其速度相同，求其运动时候的最短距离。

思路：
对于两个相同长度的向量，其距离按照时间为自变量构成一个二次函数。
那么对于两只狗每次取相同长度的直线来计算距离，然后推下去。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>
using namespace std;const int maxn = 1e5 + 7;struct Point {double x,y;
}p1[maxn],p2[maxn];double dis(Point a,Point b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}Point get(Point a,Point b,double l) { //获取向量(a,b)长度为l的一段Point ans;double len = dis(a,b);double ex = (b.x - a.x) / len,ey = (b.y - a.y) / len;ans.x = a.x + ex * l;ans.y = a.y + ey * l;return ans;
}double solve(Point a1,Point b1,Point a2,Point b2) { //计算最短距离double L1 = dis(a1,b1),L2 = dis(a2,b2);double ex1 = (b1.x - a1.x) / L1,ey1 = (b1.y - a1.y) / L1;double ex2 = (b2.x - a2.x) / L2,ey2 = (b2.y - a2.y) / L2;double a = (ex1 - ex2) * (ex1 - ex2) + (ey1 - ey2) * (ey1 - ey2);double b = 2 * ((a1.x - a2.x) * (ex1 - ex2) + (a1.y - a2.y) * (ey1 - ey2));double c = (a1.x - a2.x) * (a1.x - a2.x) + (a1.y - a2.y) * (a1.y - a2.y);if(a == 0) {return min(dis(a1,a2),dis(b1,b2));}double x = -b / (2 * a);if(x < 0 || x > L1) {return min(dis(a1,a2),dis(b1,b2));}return sqrt(a * x * x + b * x + c);
}int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%lf%lf",&p1[i].x,&p1[i].y);}int m;scanf("%d",&m);for(int i = 1;i <= m;i++) {scanf("%lf%lf",&p2[i].x,&p2[i].y);}int i = 2,j = 2;double mi = 1e9;while(i <= n && j <= m) {double l1 = dis(p1[i - 1],p1[i]),l2 = dis(p2[j - 1],p2[j]);if(fabs(l1 - l2) < 1e-8) {mi = min(mi,solve(p1[i - 1],p1[i],p2[j - 1],p2[j]));i++;j++;}else if(l1 < l2) {Point now = get(p2[j - 1],p2[j],l1);mi = min(mi,solve(p1[i - 1], p1[i], p2[j - 1], now));i++;p2[j - 1] = now;}else if(l1 > l2) {Point now = get(p1[i - 1],p1[i],l2);mi = min(mi,solve(p1[i - 1],now,p2[j - 1],p2[j]));j++;p1[i - 1] = now;}}printf("%.10f\n",mi);return 0;
}