OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【JSOI2008】球形空间产生器

【题目描述】

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

【输入】

第一行是一个整数,n。接下来的n+1行,每行有n个实数,表示球面上一点的n维坐标。每一个实数精确到小数点后6位,且其绝对值都不超过20000。

【输出】

有且只有一行,依次给出球心的n维坐标(n个实数),两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

【输入样例】

2

0.0 0.0

-1.0 1.0

1.0 0.0

【输出样例】

0.500 1.500

【数据范围】

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

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

【题解】

三个点确定一个圆,四个点确定一个球,……,n+1个点确定一个n维球形。我们假设中心坐标为(p1,p2,...,pn),若球形上一个点坐标为(a1,a2,...,an),另有一个点为(b1,b2,...,bn),则有:

(a1-p1)^2+(a2-p2)^2+...+(an-pn)^2=(b1-p1)^2+(b2-p2)^2+...+(bn-pn)^2

展开后得到一个关于(p1,p2,...,pn)的n元一次方程:

2(a1-b1)*p1+...+2(an-bn)*pn=a1^2-b1^2+...+an^2-bn^2

所以我们可以用一个点和另外n个点组合得到n个关于(p1,p2,...,pn)的n元一次方程,高斯消元法即可。

【代码】

第一次用Guess消元法AC题目~

http://paste.ubuntu.com/8120398/

评论

© OI技术宅 | Powered by LOFTER