【题解】[JSOI2008] 球形空间产生器 sphere 高斯消元 bzoj1013/luogu4035

题目链接在这 QvQ

“ 你要求出这个 n 维球体的球心坐标“，这使我想到的解方程……

先假设 n=2，这是一个二维平面。设圆心的坐标为 $(x,y)$，有两个坐标 $(a_1,b_1)$和 $(a_2,b_2)$，显然两个坐标的关系为：

$(x-a_1)^2+(y-b_1)^2=(x-a_2)^2+(y-b_2)^2$

考虑如何化简上面的式子。

$(x-a_1)^2-(x-a_2)^2+(y-b_1)^2-(y-b_2)^2=0$

根据完全平方公式：$(x-a_1)^2=x^2+a_1^2-2 \times x \times a_1$

$(x-a_1)^2-(x-a_2)^2=x^2+a_1^2-2 \times x \times a_1-x^2-a_2^2+2 \times x \times a_2$

$(x-a_1)^2-(x-a_2)^2=a_1^2-2 \times x \times a_1-a_2^2+2 \times x \times a_2$

$(x-a_1)^2-(x-a_2)^2=a_1^2-a_2^2-2(a_1-a_2)x$

同理，$(y-b_1)^2-(y-b_2)^2=b_1^2-b_2^2-2(b_1-b_2)y$

整理后：$a_1^2-a_2^2-2(a_1-a_2)x+b_1^2-b_2^2-2(b_1-b_2)y=0$

移项后：$a_1^2-a_2^2+b_1^2-b_2^2=2(a_1-a_2)x+2(b_1-b_2)y$

这个式子最终为：$2(a_1-a_2)x+2(b_1-b_2)y=a_1^2-a_2^2+b_1^2-b_2^2$

由于 $a_1^2-a_2^2+b_1^2-b_2^2$ 是已知的，我们将 $a_1^2-a_2^2+b_1^2-b_2^2$ 设为 $Sum$.

$2(a_1-a_2)$ 和 $2(b_1-b_2)$都是已知的项，分别设为 $a$ 和 $b$ .

所以它又变成了我们亲切的小学奥数之解方程：$ax+by=Sum$

对于二维的答案是 $(x,y)$ ，$x$ 和 $y$ 都可以通过高斯消元的模板来解出。

对于更高的维数，跟二维同理，只不过” 元” 多了几个而已。

所以就这样愉快的 A 掉了这道大水题。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register int
using namespace std;
const int N=25;
const double eps=1e-8;
double v[N][N],f[N][N],s[N],del;
int n;
inline bool Gauss(){
    for(RI k=1,i=1;i<=n;++i,k=i){
        for(RI j=i+1;j<=n;++j)if(abs(f[j][i])>abs(f[k][i]))k=j;
        if(fabs(del=f[k][i])<eps)return false;//不判就出 BUG，不知道为啥
        swap(f[i],f[k]);swap(s[i],s[k]);
        for(RI j=i;j<=n;++j)f[i][j]/=del;s[i]/=del;
        for(k=1;k<=n;++k)if(k!=i){
            del=f[k][i];
            for(RI j=i;j<=n;++j)f[k][j]-=f[i][j]*del;
            s[k]-=s[i]*del;
        }
    }return true;
}
int main(){
    scanf("%d",&n);
    for(RI i=1;i<=n+1;++i)for(RI j=1;j<=n;++j)scanf("%lf",&v[i][j]);
    for(RI i=1;i<=n;++i)
       for(RI j=1;j<=n;++j){
           s[i]+=(v[i][j]*v[i][j]-v[i+1][j]*v[i+1][j]);//求上面的 "Sum"
           f[i][j]=2*(v[i][j]-v[i+1][j]);//求上面的 "a"、"b"等
       }
    Gauss();
    for(RI i=1;i<n;++i)printf("%.3lf ",s[i]);//注意输出格式!
    printf("%.3lf",s[n]);
    return 0;
}

这题啥都好，就是输出格式有点制杖…… 请各位小心……