首页 > 代码库 > HDU 3571 N-dimensional Sphere( 高斯消元+ 同余 )
HDU 3571 N-dimensional Sphere( 高斯消元+ 同余 )
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)
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)
(It‘s guaranteed that all coordinate components of the answer are integers and there is only one solution and |Xi| <= 10^17)
Sample Input
2
2
1 0
-1 0
0 1
3
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|1typedef long long LL;typedef pair<int,int>pii;#define X first#define Y secondconst int oo = 1e9+7;const double PI = acos(-1.0);const double eps = 1e-6 ;const int N = 55;#define mod 200000000000000003LL#define dif 100000000000000000LLLL Mod(LL x) { if (x >= mod) return x - mod; return x;}LL mul(LL a, LL b) { LL res; for (res = 0; b; b >>= 1) { if (b & 1) 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 = 1 , y = 0 ; 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 = 0 ; 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 = 0 ; j <= n ; ++j ) swap( g[i][j] , g[r][j] ) ; LL INV = inv( g[i][i] , mod ); for( int k = i + 1 ; 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 - 1 ; i >= 0 ; --i ){ for( int j = i + 1 ; 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 , 0 , sizeof g ); for( int i = 0 ; i <= n ; ++i ) { for( int j = 0 ; j < n ; ++j ) { scanf("%I64d",&A[i][j]); A[i][j] += dif ; } } for( int i = 0 ; i < n ; ++i ){ for( int j = 0 ; j < n ; ++j ){ g[i][j] = Mod( A[n][j] - A[i][j] + mod ); g[i][j] = mul( g[i][j] , 2 ) ; 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[0][n]-dif); for( int i = 1 ; i < n ; ++i ){ printf(" %I64d",g[i][n]-dif); }puts("");}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int cas = 1 , _ ; scanf("%d",&_ ); while( _-- ){ printf("Case %d:\n",cas++); Run(); }}
HDU 3571 N-dimensional Sphere( 高斯消元+ 同余 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。