BZOJ-1013-球形空间产生器sphere

描述

有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。

分析

• 圆上每个点到圆心的距离都相等
• n维坐标下点点之间的距离是dist = sqrt((a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2)
• 列出方程, 共有 n+1 个, 但x的幂不为1, 所以两两相减得到n个x的幂为1的方程.
• 过程
  

(x1-p11)^2 + (x2-p12)^2 + … + (xn-p1n)^2 = r^2
x1^2 - 2*x1*p11 + p11^2 + x2^2 - 2*x2*p12 + p12^2 + … - r^2 = 0

(x1^2 - 2*x1*p11) + … + (xn^2 - 2*xn*p1n) - r^2 = -(p11^2 + p12^2 + … + p1n^2) .. 1
(x1^2 - 2*x2*p21) + … + (xn^2 - 2*xn*p2n) - r^2 = -(p21^2 + p22^2 + … + p2n^2) .. 2
(x1^2 - 2*x3*p31) + … + (xn^2 - 2*xn*p3n) - r^2 = -(p31^2 + p32^2 + … + p3n^2) .. 3
(x1^2 - 2*x4*p41) + … + (xn^2 - 2*xn*p4n) - r^2 = -(p41^2 + p42^2 + … + p4n^2) .. 4
(x1^2 - 2*x5*p51) + … + (xn^2 - 2*xn*p5n) - r^2 = -(p51^2 + p52^2 + … + p5n^2) .. 5
…
(xn^2 - 2*xn*p{n+1}1) + … - r^2 = -(p{n+1}1^2 + p{n+1}2^2 + … + p{n+1}n^2) .. n+1

2 - 1 : (2*x1*p11-2*x1*p21) + … + (2*xn*p1n-2*xn*p2n) = (p11^2+…+p1n^2) - (p21^2+…+p2n^2) .. 1
3 - 2 : (2*x1*p21-2*x1*p31) + … + (2*xn*p2n-2*xn*p3n) = (p21^2+…+p2n^2) - (p31^2+…+p3n^2) .. 2
….. n
=>
2(p11-p21) * x1 + … + 2(p1n-p2n) * xn = (p11^2+…+p1n^2) - (p21^2+…+p2n^2) .. 1
2(p21-p31) * x1 + … + 2(p2n-p3n) * xn = (p21^2+…+p2n^2) - (p31^2+…+p3n^2) .. 2
…
… n

代码

https://code.csdn.net/snippets/619114