BZOJ 1013 cogs 1845 [JSOI2008]球形空間産生器sphere

題目描述

　　有一個球形空間産生器能夠在n維空間中産生一個堅硬的球體。現在，你被困在了這個n維球體中，你隻知道球

面上n+1個點的坐标，你需要以最快的速度确定這個n維球體的球心坐标，以便于摧毀這個球形空間産生器。

輸入

　　第一行是一個整數n(1<=N=10)。接下來的n+1行，每行有n個實數，表示球面上一點的n維坐标。每一個實數精确到小數點

後6位，且其絕對值都不超過20000。

輸出

　　有且隻有一行，依次給出球心的n維坐标（n個實數），兩個實數之間用一個空格隔開。每個實數精确到小數點

後3位。資料保證有解。你的答案必須和标準輸出一模一樣才能夠得分。

樣例輸入

2

0.0 0.0

-1.0 1.0

1.0 0.0

樣例輸出//大坑！！！這題在BZOJ上行末不能有空格，不然PE！喪病……上面要求的6位小數也是假的，要3位

0.500 1.500

提示 

　　1、 球心：到球面上任意一點距離都相等的點。

　　2、 距離：設兩個n為空間上的點A, B的坐标為$(a_1, a_2, …, a_n)$, $(b_1, b_2, …, b_n)$，則AB的距離定義為：$dist = \sqrt{(a_1-b_1)^2 + (a_2-b_2)^2 + … + (a_n-b_n)^2}$

//部落客是LaTeX成瘾者

解題思路

　　按照提示列出方程，發現二次項好煩啊！于是第1到第n個點的方程全部與第n+1個點的方程相減，二次項就消去了，然後就直接套高斯消元吧（個人覺得高斯消元解線性方程組就是加減消元的純模拟，最多再加上了一個技巧——找目前列最大系數來消避免被卡精度）。這題不找目前列最大系數不會被卡精度，我沒寫……

源代碼

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double m[12][12]={0};
double x[12]={0};
double xy[12][12]={0},sum[12]={0};//sum[i]為第i個點到原點距離的平方;
int main()
{
    //freopen("bzoj_1013.in","r",stdin);
    //freopen("bzoj_1013.out","w",stdout);//cogs的印記
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lf",&xy[i][j]);
            sum[i]+=xy[i][j]*xy[i][j];
        }
    }
    for(int i=1;i<=n;i++)//消去二次項，形成m
    {
        for(int j=1;j<=n;j++)
        {
            m[i][j]=2*(xy[i][j]-xy[n+1][j]);
        }
        m[i][n+1]=sum[i]-sum[n+1];
    }
    //高斯消元
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(abs(m[j][i])<1e-6) continue;
            double k=m[j][i]/m[i][i];
            for(int h=i;h<=n+1;h++)
            {
                m[j][h]-=m[i][h]*k;
            }
        }
    }
    for(int i=n;i;i--)
    {
        x[i]=m[i][n+1]/m[i][i];
        for(int j=i-1;j;j--)
        {
            m[j][n+1]-=x[i]*m[j][i];
            m[j][i]=0;
        }
    }
    for(int i=1;i<n;i++) printf("%.3lf ",x[i]);
    printf("%.3lf",x[n]);
    return 0;
}