题目描述

　　有一个\(n\)维空间中的球，告诉你球面上\(n+1\)个点的坐标，求球心的坐标。

　　\(n\leq 10\)

题解

　　设\(a_{i,j}\)为第\(i\)个点的第\(j\)维坐标，\(i=0\)代表球心。

　　假设\(n=2\)：

\[ \begin{align} \sum_{i=1}^n{(a_{0,i}-a_{1,i})}^2&=\sum_{i=1}^n{(a_{0,i}-a_{2,i})}^2\\ \sum_{i=1}^na_{0,j}^2-2\sum_{i=1}^na_{0,i}a_{1,i}+\sum_{i=1}^na_{1,i}^2&=\sum_{i=1}^na_{0,j}^2-2\sum_{i=1}^na_{0,i}a_{2,i}+\sum_{i=1}^na_{2,i}^2\\ 2\sum_{i=1}^na_{0,i}a_{1,i}-\sum_{i=1}^na_{1,i}^2&=2\sum_{i=1}^na_{0,i}a_{2,i}-\sum_{i=1}^na_{2,i}^2\\ \sum_{i=1}^n2(a_{1,i}-a_{2,i})a_{0,i}-\sum_{i=1}^n(a_{2,i}^2-a_{1,i}^2)&=0 \end{align} \]

　　一共给你了\(n+1\)个点，可以构造出\(n\)个方程，可以用高斯消元解出\(n\)个未知数\(a_{0,i},\ldots ,a_{0,n}\)

　　时间复杂度：\(O(n^3)\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
            
              pii;typedef pair
             
               pll;void sort(int &a,int &b){ if(a>b) swap(a,b);}void open(const char *s){#ifndef ONLINE_JUDGE char str[100]; sprintf(str,"%s.in",s); freopen(str,"r",stdin); sprintf(str,"%s.out",s); freopen(str,"w",stdout);#endif}int rd(){ int s=0,c; while((c=getchar())<'0'||c>'9'); do { s=s*10+c-'0'; } while((c=getchar())>='0'&&c<='9'); return s;}int upmin(int &a,int b){ if(b
              
               a) { a=b; return 1; } return 0;}double a[20][20];double c[20][20];int main(){ open("bzoj1013"); int n; scanf("%d",&n); int i,j; for(i=1;i<=n+1;i++) for(j=1;j<=n;j++) scanf("%lf",&a[i][j]); for(i=1;i<=n;i++) for(j=1;j<=n+1;j++) c[i][j]=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { c[i][j]+=2*(a[1][j]-a[i+1][j]); c[i][n+1]-=a[i+1][j]*a[i+1][j]-a[1][j]*a[1][j]; } int k; double v; for(i=1;i<=n;i++) { for(j=i;j<=n;j++) if(fabs(c[j][i])>1e-9) break; if(j!=i) for(k=i;k<=n+1;k++) swap(c[i][k],c[j][k]); v=1/c[i][i]; for(j=i;j<=n+1;j++) c[i][j]*=v; for(j=1;j<=n;j++) if(j!=i&&fabs(c[j][i])>1e-9) { v=c[j][i]; for(k=i;k<=n+1;k++) c[j][k]-=c[i][k]*v; } } for(i=1;i<=n;i++) { printf("%.3f",c[i][n+1]); if(i!=n) putchar(' '); } return 0;}