资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
问题描述
空间中有n个球,这些球不相交也不相切。有m个可以视为质点的小生物,可能在某些球内,也可能在所有球之外,但不会在球面上。问这些生物从原来的地方逃逸到所有球外面的空间,至少要经过多少层球面。
输入格式
第一行两个数n、m:表示球的数量和小生物的数量;
接下来n行每行四个整数Xi、Yi、Zi和Ri:表示一个球的三维坐标和半径;
接下来m行每行三个整数Xi、Yi、Zi:表示一个生物的坐标。
输出格式
一行m个数:表示每个小生物逃逸时至少经过的球面数。
样例输入
2 2
0 0 0 2
0 0 0 4
0 0 1
0 0 3
样例输出
2 1
数据规模和约定
1<=n、m<=100,|Xi|、|Yi|、|Zi|<=10000,1<=Ri<=10000;
数据保证所有球严格不接触,小生物都不在球面上。
题解:
#include <iostream> using namespace std; struct ball { int x; int y; int z; int ri = 0;//这里我们计算虫子的时候作为标尺,所以要置0; }; struct ball ball[100];//定义球数组 struct ball Biol[100];//定义虫数组 int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> ball[i].x; cin >> ball[i].y; cin >> ball[i].z; cin >> ball[i].ri; } for (int i = 0; i < m; i++) { cin >> Biol[i].x; cin >> Biol[i].y; cin >> Biol[i].z; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int xi = (Biol[j].x - ball[i].x) * (Biol[j].x - ball[i].x); int yi = (Biol[j].y - ball[i].y) * (Biol[j].y - ball[i].y); int zi = (Biol[j].z - ball[i].z) * (Biol[j].z - ball[i].z); if (xi + yi + zi <= ball[i].ri * ball[i].ri) {//数学公式,(xBioli - xballi)^2+ //(yBioli - yballi)^2 + (zBioli - zballi)^2 <= ball[i].ri^2;即在球内。 Biol[j].ri++; } } } for (int i = 0; i < m; i++) { cout << Biol[i].ri<<' '; } return 0; }