题解 | 算法竞赛进阶指南 球形空间产生器SPHERE

思路

设圆心为,点坐标为.
因为点到圆心的距离的平方为.
这样有个式子.这些式子两两相减可以得到个元一次方程组,这样直接跑高斯消元解出圆心坐标即可.
复杂度为.

代码

#include<bits/stdc++.h>
using namespace std;
#define Re register
#define MAXN 15
#define LD long double

int N;
LD a[MAXN][MAXN], b[MAXN][MAXN];

int main(){
    scanf( "%d", &N );
    for ( int i = 1; i <= N + 1; ++i )
        for ( int j = 1; j <= N; ++j )
            scanf( "%Lf", &a[i][j] );

    for ( int i = 1; i <= N; ++i )
        for ( int j = 1; j <= N; ++j )
            b[i][j] = 2 * ( a[i + 1][j] - a[i][j] ), b[i][N + 1] += a[i + 1][j] * a[i + 1][j] - a[i][j] * a[i][j];


    for ( int i = 1; i <= N; ++i )
        for ( int j = i + 1; j <= N; ++j ){
            LD t( b[j][i] / b[i][i] );
            for ( int k = i; k <= N + 1; ++k ) b[j][k] -= t * b[i][k];
        }

    for ( int i = N; i >= 1; --i ){
        b[i][N + 1] /= b[i][i];
        for ( int j = i - 1; j >= 1; --j ) b[j][N + 1] -= b[i][N + 1] * b[j][i];
    }
    for ( int i = 1; i <= N; ++i ) printf( "%.3Lf ", b[i][N + 1] );
    return 0;
}