BZOJ1013【JSOI2008】球形空间产生器 <高斯消元>

Problem

【JSOI2008】球形空间产生器

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

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

Input

第一行是一个整数$n\;(1\le n\le10)$。
接下来的$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

给出两个定义：

• 球心：到球面上任意一点距离都相等的点。
• 距离：设两个$n$维空间上的点$A,B$的坐标为$(a_1,a_2,\cdots,a_n)$,$(b_1,b_2,\cdots,b_n)$，则$AB$的距离定义为：$dist=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+\cdots+(a_n-b_n)^2}$

标签：高斯消元

Solution

高消裸题。

将第$n+1$个点单独分出来，将其与前$n$个点分别联立形成$n$个方程，高消即可求得球心坐标。

设球心为$(x_1, x_2,\cdots,x_n)$，第$n+1$个点为$(t_1,t_2,\cdots,t_n)$。对于前$n$个点中的一个点$A$，设$A$坐标为$(a_1, a_2,\cdots,a_n)$。那么一定有

$$(a_1-x_1)^2+(a_2-x_2)^2+\cdots+(a_n-x_n)^2=(t_1-x_1)^2+(t_2-x_2)^2+\cdots+(t_n-x_n)^2$$

展开得

$$\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}x_i^2-2\sum_{i=1}^{n}a_ix_i=\sum_{i=1}^{n}t_i^2+\sum_{i=1}^{n}x_i^2-2\sum_{i=1}^{n}t_ix_i$$

移项化简

$$2\sum_{i=1}^{n}(a_i-t_i)x_i=\sum_{i=1}^{n}a_i^2-\sum_{i=1}^{n}t_i^2$$

直接高斯消元解方程组，时间复杂度$O(n^3)$。

$\bigstar$注意行末不要输出空格

Code

#include <bits/stdc++.h>
#define EPS 1e-8
using namespace std;
typedef double dnt;
int n; dnt p[15][15], f[15][15];
dnt sqr(dnt x) {return x*x;}
bool Gauss() {
    for (int i = 1, t; i <= n; i++) {
        for (t = i; t <= n; t++) if (fabs(f[t][i]) >= EPS) break;
        if (t > n) return false; swap(f[i], f[t]);
        for (int j = 1; j <= n; j++) if (i^j) {
            dnt div = f[j][i]/f[i][i];
            for (int k = 1; k <= n+1; k++)
                f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++) f[i][n+1] /= f[i][i];
    return true;
}    
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n+1; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lf", p[i]+j);
    for (int i = 1, j = n+1; i <= n; i++)
        for (int k = 1; k <= n; k++)
            f[i][k] = p[i][k]-p[j][k], 
            f[i][n+1] += (sqr(p[i][k])-sqr(p[j][k]))/2;
    Gauss();
    for (int i = 1; i <= n; i++)
        if (i^n) printf("%.3lf ", f[i][n+1]);
        else printf("%.3lf", f[i][n+1]);
    return 0;
}