描述

有一個球形空間產(chǎn)生器能夠在n維空間中產(chǎn)生一個堅硬的球體。現(xiàn)在，你被困在了這個n維球體中，你只知道球面上n+1個點(diǎn)的坐標(biāo)，你需要以最快的速度確定這個n維球體的球心坐標(biāo)，以便于摧毀這個球形空間產(chǎn)生器。

---

分析

• 
  
• 圓上每個點(diǎn)到圓心的距離都相等
• n維坐標(biāo)下點(diǎn)點(diǎ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

總結(jié)

以上是生活随笔為你收集整理的BZOJ-1013-球形空间产生器sphere的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。