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

Time Limit: 1 Sec Memory Limit: 162 MB

Description

有一个球形空间产生器能够在$n$维空间中产生一个坚硬的球体。现在，你被困在了这个$n$维球体中，你只知道球面上$n+1$个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。 　　 Input

第一行是一个整数n(1<=N=10)。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。

Output

有且只有一行，依次给出球心的$n$维坐标（$n$个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。 Sample Input

2 0.0 0.0 -1.0 1.0 1.0 0.0

Sample Output

0.500 1.500

HINT

给出两个定义：1、 球心：到球面上任意一点距离都相等的点。2、 距离：设两个n为空间上的点A, B的坐标为$(a_1,a_2,\dots ,a_n),(b_1,b_2,\dots ,b_n)$，则AB的距离定义为：$dist=sqrt((a1-b1{)}^2+(a2-b2{)}^2+\dots +(an-bn{)}^2)$

题解： 联立方程，高斯消元解方程

#include<bits/stdc++.h> #define LiangJiaJun main #define eps 1e-8 using namespace std; double ABS(double A){ if(A>eps)return A; if(-eps<A&&A<eps)return 0; return -A; } double a[14][14],x[14]; double gp[14][14]; int gauss(int equ,int var){ int k,col,max_r; for(k=1,col=1;k<=equ&&col<=var;k++,col++){ max_r=k; for(int i=k+1;i<=var;i++){ if(ABS(a[i][col])>ABS(a[max_r][col]))max_r=i; } if(ABS(a[max_r][col])<eps)return 0; if(k!=max_r){ for(int j=col;j<=var;j++)swap(a[k][j],a[max_r][j]); swap(x[k],x[max_r]); } x[k]/=a[k][col]; for(int j=col+1;j<=var;j++){ a[k][j]/=a[k][col]; } a[k][col]=1; for(int i=1;i<=equ;i++){ if(i!=k){ x[i]-=a[i][col]*x[k]; for(int j=col+1;j<=var;j++){ a[i][j]-=a[k][j]*a[i][col]; } a[i][col]=0; } } } return 0; } int n; int w33ha(){ for(int i=1;i<=n+1;i++){ for(int j=1;j<=n;j++){ scanf("%lf",&gp[i][j]); } } for(int i=1;i<=n;i++)x[i]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=-2.0*gp[i][j]+2.0*gp[n+1][j]; x[i]+=(-gp[i][j]*gp[i][j]+gp[n+1][j]*gp[n+1][j]); } } gauss(n,n); for(int i=1;i<=n;i++){ printf("%.3lf",x[i]); if(i==n)puts(""); else printf(" "); } return 0; } int LiangJiaJun(){ while(scanf("%d",&n)!=EOF)w33ha(); return 0; }