K - Keeping the Dogs Apart GYM-101550(计算几何)
程序员文章站
2024-03-17 21:22:28
...
参考: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;
}