题目描述
火星人不能忍受地球人对他们的歧视,终于发明了一种非常强大的武器: 球 形空间产生器 。球形空间产生器能产生一个 N 维球体屏障,而且这个屏障是坚 不可摧的,被困在球体内的地球人就被切断了与外界的联系。Js08 现在就被困在 了屏障中,情况十分危急,必须尽快找出并摧毁球形空间产生器。Js08 经过摸索 和碰壁,给出了球体上 N+1 个点的坐标,希望你能够帮 Js08 找出球形空间产生 器的位置——它总是位于球形空间的球心。 球体定义为到空间中定点距离等于定长的点的集合。此外,空间中两点的距 离定义为:
Distance[(x1,x2,...,xn),(y1,y2,...,yn)]=∑i=1n(xi−yi)2−−−−−−−−−−√
输入格式
输入文件第一行为整数 N,代表了空间的维度。 接下来 N+1 行,每行 N 个实数代表一个坐标。输入数据精确到小数点后 6 位。 输入数据保证输出结果唯一。
输出格式
输出一行 N 个实数代表球心的坐标,精确到小数点后三位。相邻 的数字之间用一个空格分开(行末无空格)
样例数据
样例输入
样例数据#1 2 0.0 0.0 -1.0 1.0 1.0 0.0 样例数据#2 4 24.720172 14.560868 7.592580 25.639614 24.275281 8.136164 21.498302 -12.570364 33.948090 10.669582 4.705742 -2.648426 -22.717309 3.519597 16.222675 2.425559 -9.593546 18.349904 -15.757415 10.414070
样例输出
样例数据#1 0.500 1.500 样例数据#2 5.360 5.443 6.078 4.669
数据规模
对于 40%的数据,有 N<=3。 对于 100%的数据,有 N<=10。 对于 100%的数据,输入中数字的绝对值不超过 20000。
题目分析
用二维距离,就有三个坐标,假设圆心坐标为(x0,y0),球的半径为r 则有:
(x1−x0)2+(y1−y0)2=r2(x2−x0)2+(y2−y0)2=r2(x3−x0)2+(y3−y0)2=r2
联立可得
(x1−x0)2+(y1−y0)2=(x2−x0)2+(y2−y0)2(x2−x0)2+(y2−y0)2=(x3−x0)2+(y3−y0)2
展开得
2x0(x1−x2)+2y0(y1−y2)=x21−x22+y21−y222x0(x2−x3)+2y0(y2−y3)=x22−x23+y22−y23
类推至n维,然后就交给贾老二解方程了
源代码
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=
0,bj=
1;
char x=getchar();
while(x<
'0'||x>
'9') {
if(x==
'-')bj=-
1;
x=getchar();
}
while(x>=
'0'&&x<=
'9') {
num=num*
10+x-
'0';
x=getchar();
}
return num*bj;
}
int n;
double a[
105][
105],Ans[
105],x[
105][
105];
void Simplify(
int Line) {
int Row=Line;
double Max=
abs(a[Row][Line]);
for(
int i=Line+
1; i<=n; i++)
if(
abs(a[i][Line])>Max) {
Max=
abs(a[i][Line]);
Row=i;
}
if(Row!=Line)
for(
int i=Line; i<=n+
1; i++)swap(a[Line][i],a[Row][i]);
for(
int i=Line+
1; i<=n; i++) {
double Multiple=a[i][Line]/a[Line][Line];
for(
int j=Line; j<=n+
1; j++)a[i][j]-=a[Line][j]*Multiple;
}
}
void Gauss() {
for(
int i=
1; i<=n; i++)Simplify(i);
for(
int i=n; i>=
1; i--) {
for(
int j=i+
1; j<=n; j++)a[i][n+
1]-=a[i][j]*Ans[j];
Ans[i]=a[i][n+
1]/a[i][i];
}
}
int main() {
scanf(
"%d",&n);
for(
int i=
1; i<=n+
1; i++)
for(
int j=
1; j<=n; j++)
scanf(
"%lf",&x[i][j]);
for(
int i=
1; i<=n; i++)
for(
int j=
1; j<=n; j++) {
a[i][n+
1]+=x[i][j]*x[i][j]-x[i+
1][j]*x[i+
1][j];
a[i][j]=
2*(x[i][j]-x[i+
1][j]);
}
Gauss();
for(
int i=
1; i<=n; i++)
printf(
"%0.3lf ",Ans[i]);
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-600326.html