首页 > 试题广场 >

一起来看流星雨

[编程题]一起来看流星雨
  • 热度指数:233 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛在家闷得无聊,就上网看新闻,新闻报道说今天晚上会有流星雨,所以牛牛非常高兴,就决定今天晚上约牛妹一起去看流星雨。牛妹是一个非常善于思考的同学,她看到流星划过天空,就非常好奇,随着流星的移动,流星两两之间最远的距离到底在什么时候是最小的,这个最小的距离是多少,所以他去问牛牛,牛牛同学现在光顾着看流星雨了,所以不能回答这个问题,就将这个问题交给你了,你能帮助牛牛吗?现在为了简化问题,假定 n (n<=10^4) 颗流星处于二维空间,且同一时间出发,初始时刻每颗流星会有一个坐标 (x,y) (-10^5<=x,y<=10^5) 和速度向量 (vx, vy) (-10^3<=vx,vy<=10^3)。


示例1

输入

2,[[0,0, 2, 0], [4, 0, -2, 0]]

输出

0.000

说明

第1颗流星由(0,0)点出发经过1个单位时刻到达(2, 0)坐标点,第2颗流星由(4,0)点出发经过1个单位时刻到达(2, 0)坐标点,此时两颗流星相距最远距离最小。 
示例2

输入

3,[[0, 0, 2, 0],[ 4, 0, -2, 0],[ -5, 0, 2, 0]]

输出

5.000

备注:
输入包括一个n,表示有n颗流星,接下来有n行,每行包括流星的坐标 (x,y) 和 速度向量 (vx,vy),其中这些数都是整数。
输出流星两两之间最远的距离最小的 最小距离 是多少。输出结果误差精度为3位。
function solve( n ,  star ) {
    let res=[];
    for(let i=0;i<star.length-1;i++){
        for(let j=i+1;j<star.length;j++){
            res.push(Number(calDistance(star[i],star[j])));
        }
    }
    let max=0;
    for(let re of res){
        if(re>max){
            max=re;
        }
    }
    return max;
}

function calDistance(x,y){
    let min=1<<30;
    let flag=0;
    let t=0;
    let mink;
    while(true){
        let xt=[x[0]+x[2]*t,x[1]+x[3]*t];
        let yt=[y[0]+y[2]*t,y[1]+y[3]*t];
        let k=[xt[0],xt[1],yt[0],yt[1]];
        var d=Math.abs(xt[0]-yt[0])+Math.abs(xt[1]-yt[1]);
        if(d<min){
            min=d;
            mink=k;
            flag=1;
        }else if(flag){
            break;
        }
        t++;
    }
    let re=((mink[0]-mink[2])**2+(mink[1]-mink[3])**2)**0.5;
    return re;
}
外部调用有问题,输出要求小数点后3位,但js作答的情况下始终会输出小数点后5位
发表于 2021-03-14 01:57:30 回复(1)

问题信息

难度:
1条回答 1565浏览

热门推荐

通过挑战的用户

查看代码