欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

K - Keeping the Dogs Apart GYM-101550(计算几何)

程序员文章站 2024-03-17 21:22:28
...

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