第一场-K-Keeping the Dogs Apart

程序员文章站 2022-04-07 09:04:18

...

（一）题目大意：有两只可爱的小狗分别从两个点出发沿一定的路线运动，对于每一只小狗的路线：依此给出若干个点，该小狗依次沿直线从一个点走到下一个点，已知两只小狗同时出发，且速度相等，求两只小狗在运动过程中距离的最小值（当其中一只狗到达终点时，狗狗之间的距离不再需要考虑）。

（二）解题思路：

首先我们可以直接设速度为v=1。
由于小狗在每一段的运动轨迹均为直线，我们可以把原问题化为求若狗在线段对上运动时狗之间的最短距离。

（三）细节说明：

(这里假设狗狗分别为A,B，当前A从n1走到n2，B从n3走到n4，l1=dist(n1，n2)，l2=dist(n3，n4))。

若l1==l2，则两只狗狗都刚好走完当前线段。
若l1<l2，则先求出当A走到n2时，B走到的点tmp，再求狗线段对n1-n2与n3-tmp上运动时的最短距离。
若l1>l2，类似上一种方法处理。
不断更新A和B运动时的起点和终点。

然后就是要处理两只狗在线段对上运动时的最短距离：

假设运动时间为t，我们可以求出t时刻A和B的坐标，然后便可以得到一个距离关于时间t的函数，形如d=a*t*t+b*t+c的形式。然后讨论一下a的取值以及t是否能取到最值即可以得出距离的最小值。简略过程如下：

（四）具体代码：

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
struct node{
    double x,y;
}p1[maxn],p2[maxn];
inline double dist(node n1,node n2){                              //距离
    return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));
}
node getn(node n1,node n2,double l){                              //得到中间点
    node n3;
    double len=dist(n1,n2);
    double ex1=(n2.x-n1.x)/len,ey1=(n2.y-n1.y)/len;
    n3.x=n1.x+ex1*l;
    n3.y=n1.y+ey1*l;
    return n3;
}
double getdist(node n1,node n2,node n3,node n4){                  //求运动时的距离
    double L1=dist(n1,n2),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);             //式子中的a,b,c
    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(){
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lf%lf",&p1[i].x,&p1[i].y);
    scanf("%d",&m);
    for(int i=0;i<m;i++)scanf("%lf%lf",&p2[i].x,&p2[i].y);
    int i=1,j=1;
    double _min = 1e9;
    while(j<m&&i<n){                                              //不断更新运动端点求解
        double l1=dist(p1[i-1],p1[i]),l2 =dist(p2[j-1],p2[j]);
        if(l1 == l2){
            _min=min(_min,getdist(p1[i-1],p1[i],p2[j-1],p2[j]));
            ++i,++j;
        }
        else if(l1<l2){
            node tmp=getn(p2[j-1],p2[j],l1);
            _min=min(_min,getdist(p1[i-1],p1[i],p2[j-1],tmp));
            ++ i;
            p2[j-1] = tmp;
        }
        else{
            node tmp=getn(p1[i-1],p1[i],l2);
            _min=min(_min, getdist(p1[i-1],tmp,p2[j-1],p2[j]));
            ++ j;
            p1[i-1]=tmp;
        }
    }
    printf("%.10lf\n", _min);
    return 0;
}

这tm还是一个模拟题以及一点点数学姿势？（气的是当时把题目看错然后撸了四五十分钟的代码第一场-K-Keeping the Dogs Apart

...）