[JSOI2008] 球形空间产生器题目描述输入格式输出格式样例数据数据规模题目分析源代码

125 阅读 0 评论 83 点赞

我是靠谱客的博主干净热狗，这篇文章主要介绍[JSOI2008] 球形空间产生器题目描述输入格式输出格式样例数据数据规模题目分析源代码，现在分享给大家，希望可以做个参考。

题目描述

火星人不能忍受地球人对他们的歧视，终于发明了一种非常强大的武器：球形空间产生器。球形空间产生器能产生一个 N 维球体屏障，而且这个屏障是坚不可摧的，被困在球体内的地球人就被切断了与外界的联系。Js08 现在就被困在了屏障中，情况十分危急，必须尽快找出并摧毁球形空间产生器。Js08 经过摸索和碰壁，给出了球体上 N+1 个点的坐标，希望你能够帮 Js08 找出球形空间产生器的位置——它总是位于球形空间的球心。
球体定义为到空间中定点距离等于定长的点的集合。此外，空间中两点的距离定义为：

D i s t a n c e [(x 1, x 2, . . ., x n), (y 1, y 2, . . ., y n)] = \sum i = 1 n (x i - y i) 2 - - - - - - - - - - \sqrt

输入格式

输入文件第一行为整数 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
则有：

(x 1 - x 0) 2 + (y 1 - y 0) 2 = r 2 (x 2 - x 0) 2 + (y 2 - y 0) 2 = r 2 (x 3 - x 0) 2 + (y 3 - y 0) 2 = r 2

联立可得

(x 1 - x 0) 2 + (y 1 - y 0) 2 = (x 2 - x 0) 2 + (y 2 - y 0) 2 (x 2 - x 0) 2 + (y 2 - y 0) 2 = (x 3 - x 0) 2 + (y 3 - y 0) 2

展开得

2 x 0 (x 1 - x 2) + 2 y 0 (y 1 - y 2) = x 21 - x 22 + y 21 - y 22 2 x 0 (x 2 - x 3) + 2 y 0 (y 2 - y 3) = x 22 - x 23 + y 22 - y 23

类推至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; //1.选主元(系数绝对值最大) 
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) //2.交换行(将主元调到当前行)
for(int i=Line; i<=n+1; i++)swap(a[Line][i],a[Row][i]);
for(int i=Line+1; i<=n; i++) { //3.化简该行 
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;
}

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<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; //1.选主元(系数绝对值最大) 
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) //2.交换行(将主元调到当前行)
for(int i=Line; i<=n+1; i++)swap(a[Line][i],a[Row][i]);
for(int i=Line+1; i<=n; i++) { //3.化简该行 
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;
}