[bzoj] 1013: [JSOI2008]球形空间产生器sphere

发表于   |   分类于   |  

题意

　　在$n$维空间里, 已知一个球球面上$n+1$个点的坐标, 求此球球心

传送门

分析

二维平面上的圆上的点与圆心$(a,b)$的距离为

$$(x-a)^2+(y-b)^2=r^2$$

三维空间上的球上的点与球心$(a,b,c)$的距离为

$$(x-a)^2+(y-b)^2+(z-c)^2=r^2$$

在n维空间上的球上的点与球心$(a_1,a_2,a_3,…,a_n)$的距离为

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

在二维平面上, 可由三点(不共线)确定一个圆;
在三维上四点(不共线)确定一个球;
在n维平面上, 则可由$n+1$个点(不共线)确定一个球.

相邻的两个点表示的方程

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

$$ \sum_{i=1}^{n}(y_i-a_i)^2 = r^2 $$

我们用上式减下式,可以得到

$$a_1(x_1-y_1)+a_2(x_2-y_2)+…+a_n(x_n-y_n)=\frac{ (x_1^2-y_1^2)+(x_2^2-y_2^2)+…+(x_n^2-y_n^2)}{2}$$

于是由$n+1$个方程组转化为了$n$个一维的方程组再用高斯消元法即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>

int CH , NEG ;

#include <cmath>
#include <algorithm>

#define  maxn  21LL
#define  eps   1e-6F

int n ;
double f[maxn] , a[maxn][maxn] = {0} , y ;
int i , j , k ;

int main() {
//	#define READ
true#ifdef  READ
truetruefreopen("bzoj_1013.in" ,"r",stdin ) ;
truetruefreopen("bzoj_1013.out","w",stdout) ;
true#endif
truescanf("%d", &n ) ;
truefor (i = 1 ; i <= n ; i ++ ) scanf("%lf", &f[i] ) ;
truefor (i = 1 ; i <= n ; i ++ )
truetruefor (j = 1 ; j <= n ; j ++ ) {
truetruetruescanf("%lf", &y ) ;
truetruetruea[i][j] = 2*(y-f[j]) ;
truetruetruea[i][n+1] += y*y-f[j]*f[j] ;
truetrue}
true/* Gauss */
trueint now = 1 , to ;
truedouble t ;
truefor (i = 1 ; i <= n ; i ++ ) {
truetruefor (to = now ; to <= n ; to ++ )
truetruetrueif (fabs(a[to][i]) > eps) break ;
truetrueif (to > n) continue ;
truetrueif (to != now)
truetruetruefor (j = 1 ; j <= n+1 ; j ++ )
truetruetruetruestd::swap(a[to][j] , a[now][j]) ;
truetruet = a[now][i] ;
truetruefor (j = 1 ; j <= n+1 ; j ++ )
truetruetruea[now][j] /= t ;
truetruefor (j = 1 ; j <= n ; j ++ ) {
truetruetrueif (j == now) continue ;
truetruetruet = a[j][i] ;
truetruetruefor (k = 1 ; k <= n+1 ; k ++ )
truetruetruetruea[j][k] -= t*a[now][k];
truetrue}
truetruenow ++ ;
true}
true
truefor (i = 1 ; i < n ; i ++ )
truetrueprintf("%.3lf ", a[i][n+1] ) ;
trueprintf("%.3lf\n", a[n][n+1] ) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章