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

第一场-K-Keeping the Dogs Apart

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

题目链接:点击打开链接

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

(二)解题思路:

  1. 首先我们可以直接设速度为v=1。
  2. 由于小狗在每一段的运动轨迹均为直线,我们可以把原问题化为求若狗在线段对上运动时狗之间的最短距离。
(三)细节说明:
(这里假设狗狗分别为A,B,当前A从n1走到n2,B从n3走到n4,l1=dist(n1,n2),l2=dist(n3,n4))。
  1. 若l1==l2,则两只狗狗都刚好走完当前线段。
  2. 若l1<l2,则先求出当A走到n2时,B走到的点tmp,再求狗线段对n1-n2与n3-tmp上运动时的最短距离。
  3. 若l1>l2,类似上一种方法处理。
  4. 不断更新A和B运动时的起点和终点。

然后就是要处理两只狗在线段对上运动时的最短距离:
        假设运动时间为t,我们可以求出t时刻A和B的坐标,然后便可以得到一个距离关于时间t的函数,形如d=a*t*t+b*t+c的形式。然后讨论一下a的取值以及t是否能取到最值即可以得出距离的最小值。简略过程如下:
第一场-K-Keeping the Dogs Apart

(四)具体代码:
#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...)

相关标签: 模拟题 数学