题目描述
有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。
输入格式
第一行是一个整数,n。接下来的n+1行,每行有n个实数,表示球面上一点的n维坐标。每一个实数精确到小数点后6位,且其绝对值都不超过20000。
输出格式
有且只有一行,依次给出球心的n维坐标(n个实数),两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。
题目解析
先讨论二维的情况,设圆心坐标为,则平面上某点
与圆心的距离可表示为
,有
。由圆的定义,圆上任意一点到圆心距离相等,
个点可以列出
个等式,列出等式后发现方程两边的二次项都会消去,这是一个线性方程组。这个方法可以方便地推广到高维,用高斯消元法解之。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
/************************************************************** Problem: 1013 User: frank_c1 Language: C++ Result: Accepted Time:0 ms Memory:1272 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=10+5; const double eps=1e-8; typedef double Matrix[maxn][maxn]; bool gauss_elimination(Matrix A,int n) { REP(i,0,n-1) { int r=i; REP(j,i+1,n-1) if(fabs(A[j][i]>fabs(A[r][i]))) r=j; if(r!=i) REP(j,0,n) swap(A[r][j],A[i][j]); REP(k,i+1,n-1) { double f=A[k][i]/A[i][i]; REP(j,i,n) A[k][j]-=f*A[i][j]; } } PER(i,n-1,0) { REP(j,i+1,n-1) A[i][n]-=A[j][n]*A[i][j]; if(fabs(A[i][i])<eps) return false; A[i][n]/=A[i][i]; } return true; } double st[maxn]; Matrix A; int main() { int n; double x; scanf("%d",&n); REP(i,0,n-1) scanf("%lf",&st[i]); REP(i,0,n-1) { REP(j,0,n-1) { scanf("%lf",&x); A[i][j]=2*(x-st[j]); A[i][n]+=x*x-st[j]*st[j]; } } gauss_elimination(A,n); REP(i,0,n-1) { if(i) printf(" "); printf("%.3lf",A[i][n]); } printf("\n"); return 0; } |