N-dimensional Sphere

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 668 Accepted Submission(s): 234

Problem Description

In an N-dimensional space, a sphere is defined as {(x1, x2 ... xN)| ∑(xi-Xi)^2 = R^2 (i=1,2,...,N) }. where (X1,X2…XN) is the center. You're given N + 1 points on an N-dimensional sphere and are asked to calculate the center of the sphere.

Input

The first line contains an integer T which is the number of test cases.
For each case there's one integer N on the first line.
Each of the N+1 following lines contains N integers x1, x2 ... xN describing the coordinate of a point on the N-dimensional sphere.
(0 <= T <= 10, 1 <= N <= 50, |xi| <= 10^17)

Output

For the kth case, first output a line contains “Case k:”, then output N integers on a line indicating the center of the N-dimensional sphere
(It's guaranteed that all coordinate components of the answer are integers and there is only one solution and |Xi| <= 10^17)

Sample Input

1 0

-1 0

0 1

2 2 3

0 2 3

1 3 3

1 2 4

Sample Output

Case 1:

0 0

Case 2:

1 2 3

这条题目的做法很容易想出来。

凭借 n + 1 个点代入 n 维圆公式，求圆心。

然后用第 n + 1 个方程( 设下标为n ) sigma( ( Xi - Oi )^2 ) = R^2

跟前n 个方程联立容易得到：

　　sigma( ( Xi - Oi )^2 ) = sigma( ( Yi - Oi )^2 )

两边都展开然后消掉Oi^2就得到

　　sigma( 2*( Xi - Yi )*Oi ) = sigma( Xi^2 - Yi^2 ) .

得到 n 个这样的 n 元一次方程之后就可以利用高斯消元解决。

但首先 fabs( xi ) <= 1e17 的。大数据的话显然计算过程溢出。

就用到 sigma( ai * xi ) = an ( % mod ) 来解决。求得解依然唯一。

在高斯消元的过程中会有除法，用求逆来解决。

由于数据很大，欧拉定理会溢，那么用扩展欧几里得就OK 。

然后还需要将数据加一个偏移差，把所有数据处理成正数（相当于把整个图形平移了，最后减回来不影响结果）。

避免在取余过程中把(负数+mod)%mod弄成了正。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <stack>

#include <algorithm>

using namespace std;

#define root 1,n,1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define lr rt<<1

#define rr rt<<1|1

typedef long long LL;

typedef pair<int,int>pii;

#define X first

#define Y second

const int oo = 1e9+;

const double PI = acos(-1.0);

const double eps = 1e- ;

const int N = ;

#define mod 200000000000000003LL

#define dif 100000000000000000LL

LL Mod(LL x) {

    if (x >= mod) return x - mod;

    return x;

}

LL mul(LL a, LL b) {

    LL res;

    for (res = ; b; b >>= ) {

        if (b & )

            res = Mod(res + a);

        a = Mod(a + a);

    }

    return res;

}

void e_gcd( LL a , LL b , LL &d , LL &x , LL &y ) {

    if( !b ){ d = a , x =  , y =  ; return ; }

    e_gcd( b , a%b , d , y , x );

    y -= x*(a/b);

}

LL inv( LL a , LL n ){

    LL d,x,y ;

    e_gcd(a,n,d,x,y);

    return ( x % n + n ) % n ;

}

LL A[N][N] , g[N][N];

int n ;

void Gauss() {

    for( int i =  ; i < n ; ++i ) {

        int r = i ;

        for( int j = i ; j < n ; ++j ) {

            if( g[j][i] ) { r = j ; break ; }

        }

        if( r != i ) for( int j =  ; j <= n ; ++j ) swap( g[i][j] , g[r][j] ) ;

        LL INV = inv( g[i][i] , mod );

        for( int k = i +  ; k < n ; ++k ) {

            if( g[k][i] ) {

                LL f = mul( g[k][i] , INV );

                for( int j = i ; j <= n ; ++j ) {

                    g[k][j] -= mul( f , g[i][j] );

                    g[k][j] = ( g[k][j] % mod + mod ) % mod ;

                }

            }

        }

    }

    for( int i = n -  ; i >=  ; --i ){

        for( int j = i +  ; j < n ; ++j ){

            g[i][n] -= mul( g[j][n] , g[i][j] ) , g[i][n] += mod , g[i][n] %= mod ;

        }

        g[i][n] = mul( g[i][n] , inv( g[i][i] , mod ) );

    }

}

void Run() {

    scanf("%d",&n);

    memset( g ,  , sizeof g );

    for( int i =  ; i <= n ; ++i ) {

        for( int j =  ; j < n ; ++j ) {

            scanf("%I64d",&A[i][j]);

            A[i][j] += dif ;

        }

    }

    for( int i =  ; i < n ; ++i ){

        for( int j =  ; j < n ; ++j ){

            g[i][j] = Mod( A[n][j] - A[i][j] + mod );

            g[i][j] = mul( g[i][j] ,  ) ;

            g[i][n] = Mod( g[i][n] + mul( A[n][j] , A[n][j] ) );

            g[i][n] = Mod( g[i][n] - mul( A[i][j] , A[i][j] ) + mod );

        }

    }

    Gauss();

    printf("%I64d",g[][n]-dif);

    for( int i =  ; i < n ; ++i ){

        printf(" %I64d",g[i][n]-dif);

    }puts("");

}

int main()

{

    #ifdef LOCAL

        freopen("in.txt","r",stdin);

    #endif // LOCAL

    int cas =  , _ ; scanf("%d",&_ );

    while( _-- ){

        printf("Case %d:\n",cas++); Run();

    }

}

秒客网

HDU 3571 N-dimensional Sphere( 高斯消元+ 同余 )

N-dimensional Sphere

相关文章