BZOJ1013:「JSOI2008」球形空间产生器题解

解法

这道题其实就是高斯消元裸题。依照题意可以列出形如以下的方程:

\[ \sum_{i = 1}^n (x_a [i] – x_0 [i])^2 = c \]

其中\(c\)表示球的半径。一共有\(n+1\)个这样的方程,可以考虑上下相减消掉常数,这样就构造出了一个\(n\)个方程的方程组。最终方程组:

\[ \begin{cases} 2\sum_{i = 1}^n x_1[i] x_2[i] = \sum_{i = 1}^n (x_1[i])^2 – (x_2[i])^2 \\ 2\sum_{i = 1}^n x_2[i] x_3[i] = \sum_{i = 1}^n (x_2[i])^2 – (x_3[i])^2 \\ 2\sum_{i = 1}^n x_3[i] x_4[i] = \sum_{i = 1}^n (x_3[i])^2 – (x_4[i])^2 \\ \dots \end{cases} \]

扔到高斯消元里就搞定了。

Continue reading →