根據(jù)空間4點坐標求球心坐標

1、根據(jù)空間4點坐標求球心坐標程序設計藝術與方法課程2012“達內杯”安徽省程序設計競賽Problem J 銀河系5A風景區(qū)解題報告題目原文：Description巴爾坦星是個銀河系中一個著名的觀光景點，它之所有著名，是因為巴爾坦星有四顆衛(wèi)星，而且四顆衛(wèi)星距離巴爾坦星的距離都是一樣的！某天，巴爾坦星上的居民們想知道自己星球所處的具體三維宇宙坐標，因為科技落后，巴爾坦星上的居民只有某個時刻測得的四顆衛(wèi)星的坐標。現(xiàn)在請你寫個程序幫可憐的巴爾坦星居民給自己的星球定下位吧。Input第一行是一個整數(shù) t ，表示有 t 組測試數(shù)據(jù)。（t = 30）每組數(shù)據(jù)占四行，表示四顆衛(wèi)星的坐標。每行三個實數(shù) x, y,

2、 z 表示該點的坐標為 (x,y,z)。輸入數(shù)據(jù)保證每組的數(shù)據(jù)都可以確定巴爾坦星，設巴爾坦星的坐標為(ox, oy, oz)，每顆衛(wèi)星到巴爾坦星的距離都是r。則以下不等式總是成立：-500 = ox, oy, oz = 500， 500 = r = 1000。Output對于每組數(shù)據(jù)輸出一行；Case #k: x y z 。k表示第k組數(shù)據(jù)，x, y, z 表示巴爾坦星的坐標（均保留到小數(shù)點后一位）。Sample Input11.1 0 00.1 1.0 00.1 -1.0 00.1 0 1.0Sample OutputCase #1: 0.1 0.0 0.0解題思路：本題本質上是一道空間解析

3、幾何題，其核心是利用三維空間中不共面的四個點的坐標來求球心坐標。我利用四個點到球心距離相等的性質，列出四個三元二次方程，再兩兩消去，得到三個三元一次方程，該方程組是一個線性非齊次方程組，利用系數(shù)行列式表示，并且運用克拉默法則，可以解出該方程組，方程組的解就是球心的坐標。算法：題中所要求坐標的星球有四顆衛(wèi)星，可以對應空間中的四個點，因為知道四個衛(wèi)星的坐標，所以已知這四個點的坐標，可設為A(x1,y1,z1)、B(x2,y2,z2)、C(x3,y3,z3)、D(x4,y4,z4)，設半徑為r，球心O坐標為(x,y,z)。利用四點到球心距離相等的性質得到如下四個方程。(x-x1)2+(y-y1)2

4、+(z-z1)2 =r2;(x-x2)2+(y-y2)2 +(z-z2)2 =r2;(x-x3)2+(y-y3)2 +(z-z3)2 =r2;(x-x3)2+(y-y3)2 +(z-z3)2 =r2;展開得：x2+y2+z2-2(x1x+y1y+z1z) + x12 + y12 + z12=r2; x2+y2+z2-2(x2x+y2y+z2z) + x22 + y22 + z22=r2; x2+y2+z2-2(x3x+y3y+z3z) + x32 + y32 + z32=r2; x2+y2+z2-2(x4x+y4y+z4z) + x42 + y42 + z42=r2; 分別作-、-、-得：(x

5、1-x2)x+(y1-y2)y+(z1-z2)z=12(x12-x22 + y12-x22 + z12-z22);(x3-x4)x+(y3-y4)y+(z3-z4)z=12(x32-x42 + y32-x42 + z32-z42);(x2-x3)x+(y2-y3)y+(z2-z3)z=12(x22-x32 + y22-x32 + z22-z32);其對應的系數(shù)行列式可設為：D=abca1b1c1a2b2c2則a=(x1-x2), b=(y1-y2), c=(z1-z2) a1=(x3-x4), b1=(y3-y4), c1=(z3-z4); a2=(x2-x3), b2=(y2-y3), c2

6、=(z2-z3);常數(shù)項行列式為：PQR則 P= 12(x12-x22 + y12-x22 + z12-z22); Q= 12(x32-x42 + y32-x42 + z32-z42); R= 12(x22-x32 + y22-x32 + z22-z32);現(xiàn)設Dx=PbcQb1c1Rb2c2Dy=aPca1Qc1a2Rc2DZ=abPa1b1Qa2b2R由線性代數(shù)中的克拉默法則可知：x=Dx / D;y=Dy / D;z=Dz / D;由此即可解出三元一次方程組的解，所得解也就是空間四個點所在球的球心坐標。還原至題中亦即巴爾坦星的坐標。收獲和分析：我的收獲： 在解決問題的過程中，我了解到了方

7、法和知識的重要性，在解決問題的過程中采取合適的方法將事半功倍，而這需要我們平時不斷地積累，善于使用專業(yè)課所學的知識；還有就是團隊協(xié)作的能力得到了鍛煉，本題的解答，是我和室友共同努力的結晶，是我們團隊協(xié)作的成果。關于題目的分析： 解題過程中，我曾一度陷入僵局，早先就列出了三元一次方程組，卻是利用高中時所學的代入法，解出了x, y ,z的公式，但解出的公式卻有一個致命傷，對輸入的很多組測試數(shù)據(jù)，偶爾有使公式的分母出現(xiàn)0的情況，此時公式便失去了作用，即程序有bug，這個問題是公式法算法中遲遲無法解決的。而就本題而言，采用行列式的解法和克拉默法則后，只有當空間中的四點共面時才會出現(xiàn)無解的情況，而這時才

8、會使系數(shù)行列式D值為0；通過數(shù)學我們知道，共面的四個點無法確定一個球，所以本題合理的輸入不應包括共面的四個點的坐標。有了求解球心的函數(shù)之后(以上算法編成一個函數(shù))，開始考慮規(guī)范化輸入輸出，這應當不難解決源代碼：。#include#include /fabs()、sqrt()函數(shù)#include /用于控制輸出精度#define maxnum 30using namespace std;void solve();/double distances(double x1,double y1,double z1,double h1,double h2,double h3);int main() sol

9、ve(); 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, 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;ix1y1z1x2y2z2x3y3z3x4y4z4; coutendl; a=(x1-x2); b=(y1-y2); c=(z1-z2)

10、; A=(x1*x1-x2*x2); B=(y1*y1-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是系數(shù)行列式 ，運用克拉默法則 doub

11、le D=a*b1*c2+a2*b*c1+c*a1*b2-(a2*b1*c+a1*b*c2+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;it;i+) if(answeri3=0) cout第i+1組輸入的四個點不符合要求endl; /四點共面或者等于零都不符合 e