CSU-1407: 最短距离

时间：2014-09-03 16:50:06 收藏：0 阅读：325

Description

两个点A, B均在做匀速直线运动。给出t = 0时刻A, B的坐标，以及A, B的速度，计算t ≥ 0时两个点的距离的最小值。

Input

输入的第一行包含一个整数T (1 ≤ T ≤ 200)，表示一共有T组测试数据。

对于每组测试数据，第一行包含4个整数xA, yA, vAx, vAy (-103 ≤ xA, yA, vAx, vAy ≤ 103)，表示t = 0时刻A的坐标为(xA, yA)，A的速度在x轴方向上的分量为vAx，在y轴上的分量为vAy。第二行包含四个整数xB, yB, vBx, vBy (-103 ≤ xB, yB, vBx, vBy ≤ 103)，以相同的方式给出了B的各项属性。

Output

对于每组测试数据，输出t ≥ 0时两个点距离的最小值，保留8位小数。

Sample Input

6
0 0 0 0
0 1 0 1
0 0 -1 1
0 0 1 -1
0 1 1 0
2 0 0 1
0 1 1 0
2 0 1 0
0 0 -1 1
1 1 1 -1
997 997 -1000 -1000
-1000 -1000 1000 1000

Sample Output

HINT

Source

中南大学第八届大学生程序设计竞赛

/在t时刻求出A，B，的坐标，然后用距离公式求出d=A，B的距离，是一个关于t的二元一次方程，根据已知条件求出a,b,c，判断，最简单的办法直接
1. 求出顶点坐标，也就是-B/2/A。如果这个数大于等于0，那么求顶点函数值
2. 求0那个点的函数值
将1和2两个值取min就可以了。注意，如果1中A等于0，也是不需要考虑1这种情况的。抛物线顶点（-2*a/b, sqrt（b*b-4*a*c)/4*a;)

#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 0xfffffff
int main()
{
    int t,xa,ya,vax,vay,xb,yb,vbx,vby,i,j;
    double a,b,c,s,ans;
    scanf("%d",&t);
    while(t--)
    {
        s=0;
        ans=maxn;
        scanf("%d%d%d%d",&xa,&ya,&vax,&vay);
        scanf("%d%d%d%d",&xb,&yb,&vbx,&vby);
        a=(vax-vbx)*(vax-vbx)+(vay-vby)*(vay-vby);
        b=2*((xa-xb)*(vax-vbx)+(ya-yb)*(vay-vby));
        c=(xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);
        //printf("%lf %lf %lf\n",a,b,c);
        if(a==0) printf("%.8lf\n",sqrt(c));
        else
        {
        s=-b/a/2;
        //printf("%lf\n",s);
        if(s>0) ans=(4*a*c-b*b)/4/a;
       // printf("%lf\n",ans);
        ans=sqrt(ans);
        c=sqrt(c);
        printf("%.8lf\n",ans>c?c:ans);
        }
    }
    return 0;
}

原文：http://blog.csdn.net/u012773338/article/details/39029273