根据空间4点坐标求球心坐标

1、.程序设计艺术与方法课程2012“达内杯”安徽省程序设计竞赛Problem J 银河系 5A 风景区解题报告题目原文：Description巴尔坦星是个银河系中一个著名的观光景点，它之所有著名，是因为巴尔坦星有四颗卫星，而且四颗卫星距离巴尔坦星的距离都是一样的！ 某天，巴尔坦星上的居民们想知道自己星球所处的具体三维宇宙坐标， 因为科技落后， 巴尔坦星上的居民只有某个时刻测得的四颗卫星的坐标。现在请你写个程序帮可怜的巴尔坦星居民给自己的星球定下位吧。Input第一行是一个整数t ，表示有 t 组测试数据。 （ t <= 30）每组数据占四行，表示四颗卫星的坐标。每行三个实数 x, y, z

2、表示该点的坐标为 (x,y,z)。输入数据保证每组的数据都可以确定巴尔坦星，设巴尔坦星的坐标为(ox, oy, oz) ，每颗卫星到巴尔坦星的距离都是r。则以下不等式总是成立：-500 <= ox, oy, oz <= 500， 500 <= r <= 1000。Output对于每组数据输出一行； "Case #k: x y z" 。k 表示第 k 组数据 ，x, y, z 表示巴尔坦星 的坐标（均保留到小数点后一位） 。Sample Input11.1000.1 1.0 00.1 -1.0 00.1 0 1.0Sample OutputCase #

3、1: 0.1 0.0 0.0解题思路：本题本质上是一道空间解析几何题，其核心是利用三维空间中不共面的四个点的坐标来求球心坐标。我利用四个点到球心距离相等的性质，列出四个三元二次方程，再两两消去，得到三个三元一次方程，该方程组是一个线性非齐次方程组，利用系数行列式表示， 并且运用克拉默法则， 可以解出该方程组， 方程组的解就是球心的坐标。.算法：题中所要求坐标的星球有四颗卫星，可以对应空间中的四个点，因为知道四个卫星的坐标，所以已知这四个点的坐标，可设为 A(x1,y1,z1)、B(x2,y2,z2)、C(x3,y3,z3)、D(x4,y4,z4)，设半径为 r，球心 O 坐标为 (x,y,z)

4、。利用四点到球心距离相等的性质得到如下四个方程。(x -x1) 2 +(y -y1) 2+(z -z1) 2=r 2 ;(x -x2) 2 +(y -y2) 2+(z -z2) 2=r 2 ;(x -x3) 2 +(y-y3) 2+(z -z3) 2=r 2 ;(x -x3) 2 +(y-y3) 2+(z -z3) 2=r 2 ;展开得：x2+y2+z22+ y12+ z12=r2;- 2(x1x+y1y+z1z) + x11x2+y2+z22+ y22+ z22=r2;2- 2(x2x+y2y+z2z) + x2x2+y2+z22+ y322=r2;3- 2(x3x+y3y+z3z) + x

5、3+ z3x2+y2+z22+ y42+ z42=r2;4- 2(x4x+y4y+z4z) + x4分别作 -、 -、 -得：12342312-x22+y12-x22+z12-z22 );(x1-x2)x+(y1-y2)y+(z1-z2)z=(x1212-x42+y32-x42+z32-z42 );(x3-x4)x+(y3-y4)y+(z3-z4)z=(x3212-x32+y22-x32+z22-z32 );(x2-x3)x+(y2-y3)y+(z2-z3)z=(x22其对应的系数行列式可设为：D=abca1b1c1a2b2c2则 a=(x1-x2), b=(y1-y2), c=(z1-z2)

6、 a1=(x3-x4), b1=(y3-y4), c1=(z3-z4);.a2=(x2-x3), b2=(y2-y3),c2=(z2-z3);常数项行列式为：PQR则 P= 12(x12 - x2 2 + y12 - x22 + z12 - z22 );Q= 12(x3 2 - x42 + y32 - x42 + z32 - z42 );R= 12(x22 - x32 + y22 -x32 + z22 - z32 );现设 Dx=PbcQb1c1Rb2c2Dy=aPca1Qc1a2Rc2DZ=abPa1b1Qa2b2R由线性代数中的克拉默法则可知：x=Dx / D;y=Dy / D;.z=Dz

7、 / D;由此即可解出三元一次方程组的解，所得解也就是空间四个点所在球的球心坐标。还原至题中亦即巴尔坦星的坐标。收获和分析 ：我的收获：在解决问题的过程中，我了解到了方法和知识的重要性，在解决问题的过程中采取合适的方法将事半功倍，而这需要我们平时不断地积累，善于使用专业课所学的知识；还有就是团队协作的能力得到了锻炼，本题的解答， 是我和室友共同努力的结晶，是我们团队协作的成果。关于题目的分析：解题过程中， 我曾一度陷入僵局，早先就列出了三元一次方程组，却是利用高中时所学的代入法，解出了x, y ,z的公式，但解出的公式却有一个致命伤，对输入的很多组测试数据，偶尔有使公式的分母出现0 的情况，此

8、时公式便失去了作用，即程序有bug ，这个问题是公式法算法中迟迟无法解决的。而就本题而言， 采用行列式的解法和克拉默法则后，只有当空间中的四点共面时才会出现无解的情况，而这时才会使系数行列式D 值为 0；通过数学我们知道， 共面的四个点无法确定一个球， 所以本题合理的输入不应包括共面的四个点的坐标。有了求解球心的函数之后 ( 以上算法编成一个函数 ) ，开始考虑规范化输入输出，这应当不难解决源代码：。#include<iostream>#include<cmath>/fabs() 、 sqrt() 函数#include<iomanip>/ 用于控制输出精度#

9、define maxnum 30using namespace std;void solve();/double distances(double x1,double y1,double z1,double h1,double h2,double h3); int main()solve();system("PAUSE");return 0;void solve().double answermaxnum4;int i,t, s=0 ;cin >> t;double x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4;double a,b,c

10、,A,B,C, a1,b1,c1,A1,B1,C1,a2,b2,c2,A2,B2,C2;double P,Q,R;double x, y, z;for(i=0;i<t;i+)/ 输入四个点的坐标cin>>x1>>y1>>z1>>x2>>y2>>z2>>x3>>y3>>z3>>x4>>y4>>z4; cout<<endl;a=(x1-x2);b=(y1 -y2);c=(z1-z2);A=(x1*x1 -x2*x2);B=(y1*y1 -

11、y2*y2);C=(z1*z1-z2*z2);a1=(x3-x4);b1=(y3-y4);c1=(z3-z4);A1=(x3*x3-x4*x4);B1=(y3*y3 -y4*y4);C1=(z3*z3-z4*z4);a2=(x2-x3);b2=(y2-y3);c2=(z2-z3);A2=(x2*x2-x3*x3);B2=(y2*y2 -y3*y3);C2=(z2*z2-z3*z3);P=(A+B+C)/2;Q=(A1+B1+C1)/2;R=(A2+B2+C2)/2;/D 是系数行列式，运用克拉默法则double D=a*b1*c2+a2*b*c1+c*a1*b2-(a2*b1*c+a1*b*c

12、2+a*b2*c1);double Dx=P*b1*c2+b*c1*R+c*Q*b2-(c*b1*R+P*c1*b2+Q*b*c2);double Dy=a*Q*c2+P*c1*a2+c*a1*R-(c*Q*a2+a*c1*R+c2*P*a1);double Dz=a*b1*R+b*Q*a2+P*a1*b2-(a2*b1*P+a*Q*b2+R*b*a1);x = Dx/D；y = Dy/D；z = Dz/D ; answeri0=x;answeri1=y;answeri2=z;answeri3=D; / 判断四点是否共面 :for(i=0;i<t;i+)if(answeri3=0)cout<<" 第 "<<i+1<<" 组输入的四个点不符合要求"<<endl;/ 四点共面或者等于零都不符合elsecout << "Case #" <<i+1 << " o" <<setiosflags(ios:fixed) << setprecision(1)<<answer