Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

10/10
21:39
线性代数

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

00:00/00:00

11735326448d29be99l   1132956622013bb249l

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

 第一行是一个整数,n。接下来的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   ♦♦♦♦♦♦

数据规模:

对于40%的数据,1<=n<=3

对于100%的数据,1<=n<=10

提示:给出两个定义:

1、 球心:到球面上任意一点距离都相等的点。

2、 距离:设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn),则AB的距离定义为:dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 )

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

以二维空间为例,(a1,b1)(a2,b2)在圆上,圆心是(x,y),

则(a1-x)^2+(b1-y)^2=(a2-x)^2+(b2-y)^2

a1^2-2a1x+b1^2-2b1y=a2^2-2a2x+b2^2-2b2y

2(a1-a2)x+2(b1-b2)y=a1^2-a2^2+b1^2-b2^2

这样就可以根据两个点列出一个线性方程,于是就可以根据第一个点和接下来的n个点列出一个线性方程组,高斯消元就可以啦w

c++:

pascal:

89

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