藍橋杯試題 算法訓練 小生物的逃逸 C/C++

試題 算法訓練 小生物的逃逸

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

　　空間中有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；

　　資料保證所有球嚴格不接觸，小生物都不在球面上。

思路：本題主要是考公式，判定小生物是在球的裡面還是外面，而判定的方法是各坐标軸的內插補點的平方相加小于或者等于球面半徑的平方則為在球當中，否則不在（也就不需要穿過此球面）

x1、y1、z1代表球，r為球的面積；x2、y2、z2代表小生物坐标

（x1-x2）（x1-x2）+（y1-y2）（y1-y2）+（z1-z2）（z1-z2）<=rr為在球面當中，否則不在（寫一個詳細的公式）

代碼如下：

#include<iostream>
using namespace std;
main(){
	int n,m,a[105][4],b[105][3],i,j,k=0,k1=0;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
	}
	for(j=0;j<m;j++){
		cin>>b[j][0]>>b[j][1]>>b[j][2];
	}
	for(j=0;j<m;j++){
		for(i=0;i<n;i++){
			k1=(b[j][0]-a[i][0])*(b[j][0]-a[i][0]);
			k1+=(b[j][1]-a[i][1])*(b[j][1]-a[i][1]);
			k1+=(b[j][2]-a[i][2])*(b[j][2]-a[i][2]);
			if(k1<=a[i][3]*a[i][3]){
				k++;
			}
		}
		cout<<k<<" ";
		k=0;
	}
}