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

程序设计艺术与方法课程 2012“达内杯”安徽省程序设计竞赛 Problem J 银河系5A风景区 解题报告 题目原文： Description 巴尔坦星是个银河系中一个著名的观光景点，它之所有著名，是因为巴尔坦星有四颗卫星，而且四颗卫星距离巴尔坦星的距离都是一样的！某天，巴尔坦星上的居民们想知道自己星球所处的具体三维宇宙坐标，因为科技落后，巴尔坦星上的居民只有某个时刻测得的四颗卫星的坐标。现在请你写个程序帮可怜的巴尔坦星居民给自己的星球定下位吧。 Input 第一行是一个整数 t ，表示有 t 组测试数据。（t = 30） 每组数据占四行，表示四颗卫星的坐标。 每行三个实数 x, y, z 表示该点的坐标为 (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 Input 1 1.1 0 0 0.1 1.0 0 0.1 -1.0 0 0.1 0 1.0 Sample Output Case #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)。利用四点到球心距离相等的性质得到如下四个方程。 (x-x1)2+(y-y1) (x-x2)2+(y (x-x3)2+(y (x-x3)2+(y 展开得： x2+y2+z2-2(x1x+y1y+z1z) + x12 + y12 + z12 x2+y2+z2-2(x2x+y2y+z2z) + x22 + y22 + z22 x2+y2+z2-2(x3x+y3y+z3z) + x32 + y32 + z32=r x2+y2+z2-2(x4x+y4y+z4z) + x42 + y42 + z42 分别作 eq \o\ac(○,1)- eq \o\ac(○,2)、 eq \o\ac(○,3)- eq \o\ac(○,4)、 eq \o\ac(○,2)- eq \o\ac(○,3)得： (x1-x2)x+(y1-y2)y+(z1-z2)z=12(x12-x22 (x3-x4)x+(y3-y4)y+(z3-z4)z=12(x32-x42 (x2-x3)x+(y2-y3)y+(z2-z3)z=12(x22-x32 其对应的系数行列式可设为： D=a 则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=(z2-z3); 常数项行列式为： P 则 P= 12(x12-x2 Q= 12(x32-x4 R= 12(x22-x3 现设Dx= P Dy=a DZ=a 由线性代数中的克拉默法则可知： x=Dx / D; y=Dy / D; z=Dz / D; 由此即可解出三元一次方程组的解，所得解也就是空间四个点所在球的球心坐标。还原至题中亦即巴尔坦星的坐标。 收获和分析： 我的收获： 在解决问题的过程中，我了解到了方法和知识的重要性，在解决问题的过程中采取合适的方法将事半功倍，而这需要我们平时不断地积累，善于使用专业课所学的知识；还有就是团队协作的能力得到了锻炼，本题的解答，是我和室友共同努力的结晶，是我们团队协作的成果。 关于题目的分析： 解题过程中，我曾一度陷入僵局，早先就列出了三元一次方程组，却是利用高中时所学的代入法，解出了x, y ,z的公式，但解出的公式却有一个致命伤，对输入的很多组测试数据，偶尔有使公式的分母出现0的情况，此时公式便失去了作用，即程序有bug，这个问题是公式法算法中迟迟无法解决的。而就本题而言，采用行列式的解法和克拉默法则后，只有当空间中的四点共面时才会出现无解的情况，而这时才会使系数行列式D值为0；通过数学我们知道，共面的四