[BZOJ 1013][JSOI2008]球形空间产生器sphere：高斯消元

本文主要是介绍[BZOJ 1013][JSOI2008]球形空间产生器sphere：高斯消元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

设球心坐标为（x1,x2,x3,…,xn），某个点的坐标为(y1,y2,y3,…,yn），点到球心的距离为L，那么

L 2 = (y 1 2 - 2 * x 1 * y 1 + x 1 2) + (y 2 2 - 2 * x 2 * y 2 + x 2 2) + (y 3 2 - 2 * x 3 * y 3 + x 3 2) + . . . + (y n 2 - 2 * x n * y n + x n 2)

$L^{2}=({y_{1}}^{2}-2*x_{1}*y_{1}+{x_{1}}^{2})+({y_{2}}^{2}-2*x_{2}*y_{2}+{x_{2}}^{2})+({y_{3}}^{2}-2*x_{3}*y_{3}+{x_{3}}^{2})+...+({y_{n}}^{2}-2*x_{n}*y_{n}+{x_{n}}^{2})$

同理可以得到其他点与球心距离的式子，n+1个式子相减，刚好消掉所有 ${x_{i}}^{2}$ 并得到n个式子

/*
User:Small
Language:C++
Problem No.:1013
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=15;
const double eps=1e-6; 
double a[M][M],st[M];
int n;
bool gauss_jordan(){for(int i=0;i<n;i++){int p=i;for(int j=i+1;j<n;j++)if(fabs(a[j][i])>fabs(a[p][i])) p=j;swap(a[i],a[p]);if(fabs(a[i][i])<eps) return 0;//无解或无穷解 for(int j=i+1;j<=n;j++) a[i][j]/=a[i][i];for(int j=0;j<n;j++){if(i==j) continue;for(int k=i+1;k<=n;k++){a[j][k]-=a[j][i]*a[i][k];}}}return 1;
}
int main(){freopen("data.in","r",stdin);//scanf("%d",&n);for(int i=0;i<n;i++) scanf("%lf",&st[i]);for(int i=0;i<n;i++){double x;for(int j=0;j<n;j++){scanf("%lf",&x);a[i][j]=2*(x-st[j]);a[i][n]+=x*x-st[j]*st[j];}}gauss_jordan();for(int i=0;i<n;i++){printf("%.3lf%c",a[i][n],i==n-1?'\n':' ');}return 0;
}