BZOJ1013 [JSOI2008]球形空间产生器sphere[高消]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define dbg(x) cerr << #x << " = " << x <<endl
 7 using namespace std;
 8 typedef long long ll;
 9 typedef long double db;
10 typedef pair<int,int> pii;
11 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
12 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
13 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
14 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
15 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
16 template<typename T>inline T read(T&x){
17     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c==‘-‘)f=1;
18     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
19 }
20 const int N=10+4;
21 db A[N][N],B[N][N];
22 int n,maxl;
23 
24 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
25     read(n);
26     for(register int i=1;i<=n+1;++i)for(register int j=1;j<=n;++j)scanf("%Lf",&B[i][j]);
27     for(register int i=1;i<=n;++i){
28         for(register int j=1;j<=n;++j)A[i][j]=2*(B[n+1][j]-B[i][j]);
29         for(register int j=1;j<=n;++j)A[i][n+1]+=B[n+1][j]*B[n+1][j]-B[i][j]*B[i][j];
30     }
31     for(register int i=1;i<=n;++i){
32         maxl=i;
33         for(register int j=i+1;j<=n;++j)if(fabs(A[j][i])>fabs(A[maxl][i]))maxl=j;
34         if(maxl^i)swap(A[maxl],A[i]);
35         for(register int l=1;l<=n;++l)if(l^i)
36             for(register int j=n+1;j>=i;--j)
37                 A[l][j]-=A[l][i]/A[i][i]*A[i][j];
38     }
39     for(register int i=1;i<=n;++i)printf("%.3Lf\n",A[i][n+1]/A[i][i]);
40     return 0;
41 }