BZOJ 1013 [JSOI2008] 球形空间产生器 sphere

发布于 2017-07-05  140 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1013

题意:给出 n 维球面上 n+1 个点的坐标,求确定圆心坐标


约定:

对于 n 维空间的一个点的坐标,我们以一个形如下式的 行向量去表示

$$\begin{bmatrix}
a_1 & a_2 & ... & a_n
\end{bmatrix}$$


考虑 n+1 个点两两到圆心的距离都是相同的,写成连等式的形式,每个等号左右都可以列出一个方程,这样可以列出 n 个方程,显然可以算出 n 个未知量...

形式的说,设球心坐标为\(\begin{bmatrix}x_1 & x_2 & ... & x_n\end{bmatrix}\),

当前点 i 坐标为\(\begin{bmatrix}a_1 & a_2 & ... & a_n\end{bmatrix}\),

点 i+1 坐标为\(\begin{bmatrix}b_1 & b_2 & ... & b_n\end{bmatrix}\)

列出的方程是这个样子的:

$$(a_1-x_1)^2+(a_2-x_2)^2+...+(a_n-x_n)^2=(b_1-x_1)^2+(b_2-x_2)^2+...+(b_n-x_n)^2$$

$$a_1^2-2a_1x_1+a_2^2-2a_2x_2+...+a_n^2-2a_nx_n=b_1^2-2b_1x_1+b_2^2-2b_2x_2+...+b_n^2-2b_nx_n$$

$$2(b_1-a_1)x_1+2(b_2-a_2)x_2+...+2(b_n-a_n)x_n=b_1^2-a_1^2+b_2^2-a_2^2+...+b_n^2-a_n^2$$

不卡精度真是开心啊... 写题解时间比写代码时间长系列....

 


一个非常弱的准退役OIER