高维碰撞

NC231898. 高维碰撞

描述

在高维宇宙中，两星系相互碰撞后会相互穿过对方，星系的运动不会受到影响，但里面的生物可要遭殃了，你作为高维宇宙的神，希望自己能告诉星系中的生物，星系碰撞，即两星系首次接触，会在什么时刻发生。
星系可以看作高维空间的球体，已知 $0$ 时刻两星系的状态，求出两星系碰撞的时间。

定义 $1$ ：设 $n$ 维球体的球心为 $(x_1,x_2,\cdots,x_n)$ 半径为 $r$ ，则其表达式为 $\sum_{i=1}^n{(y_i-x_i)^2} = r^2$ 。

定义 $2$ ：有两个 $n$ 维球体 $A$ 和 $B$ ， $A$ 的球心为 $(x_{A1}, x_{A2}, \cdots, x_{An})$ 半径为 $r_A$ ， $B$ 的球心为 $(x_{B1}, x_{B2}, \cdots, x_{Bn})$ 半径为 $r_B$ ，则两个球体接触当且仅当 $\sqrt{\sum_{i=1}^n{(x_{Ai}-x_{Bi})^2}}=r_A+r_B$ 。

输入描述

第一行输入一个整数  表示有  组测试数据。

对于第  组测试数据：

第  行输入一个整数  代表维度数。

第  行输入两个整数  代表两个星系的半径。

第  行输入  个整数  表示第一个星系的坐标。

第  行输入  个整数  表示第二个星系的坐标。

第  行输入  个整数  表示第一个星系的单位速度。

第  行输入  个整数  表示第二个星系的单位速度。

输出描述

若两个星系永不碰撞，则输出 "inf"（不包含引号），否则输出答案的整数部分。

示例1

输入:

1
4
1 1
0 0 0 0
10 10 10 10
0 0 0 0
1 1 1 1

输出:

-11

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 16ms, 内存消耗: 392K, 提交时间: 2022-01-28 15:40:44

#include<bits/stdc++.h>
#define N 20
#define err 1e-11
using namespace std;
typedef long long ll;
ll T,n;
double ra,rb,va[N],vb[N],a[N],b[N],A,B,C;
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        A=B=C=0.0;
        cin>>ra>>rb;
        for(ll i=1;i<=n;i++) cin>>a[i];
        for(ll i=1;i<=n;i++) cin>>b[i];
        for(ll i=1;i<=n;i++) cin>>va[i];
        for(ll i=1;i<=n;i++) cin>>vb[i];
        for(ll i=1;i<=n;i++){
            A+=(va[i]-vb[i])*(va[i]-vb[i]);
            C+=(a[i]-b[i])*(a[i]-b[i]);
            B+=2*(va[i]-vb[i])*(a[i]-b[i]);
        }
        C-=(ra+rb)*(ra+rb);
        double dt=B*B-4*A*C;
        if(dt+err<0){
            cout<<"inf"<<endl;
            continue;
        }
        double ans=(-B-sqrt(dt))/(2.0*A);
        cout<<ll(ans)<<endl;
    }
    return 0;
}

上一题

下一题

详情