Luogu4035 [JSOI2008]球形空间产生器

tony102

2021 年 01 月 11 日

1418 次浏览

暂无评论

665字数

题解

[Link](https://www.luogu.com.cn/problem/P4035)

## Sol

似乎很久都没有发题解了

看题，现在在 $n$ 维空间中我们要求出这个球的球心。我们可以设球心的坐标为 $(r_1, r_2, \dots, r_n)$ 。根据给出的定义的距离公式，我们可以得到半径和一个球面上的点与球心的关系，即:

$$
R = \sqrt{\sum \left( a_i-r_i\right)^2}
$$

有根号项，同时平方一下，并且把二项式展开

$$
R^2= \sum a_{i}^2 - 2\sum{a_i\times r_i + \sum r_i^2}
$$

那么因为只有关$a_i$的先均可以视为常数项，将其移至等号右边，这样就得到了一个关于$r_i$的$n+1$一个方程。高斯消元求解即可

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 10 + 5;
const int eps = 1e-7;

int n;
double a[SIZE][SIZE];

int main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	scanf("%d", &n); ++ n;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j < n; ++ j) {
			scanf("%lf", &a[i][j]);
			a[i][n + 1] -= a[i][j] * a[i][j]; a[i][j] *= -2.00;
		}
		a[i][n] = 1;
	}
	for (int i = 1, cur; i <= n; ++ i) {
		cur = i;
		for (int j = i + 1; j <= n; ++ j) {
			if (fabs(a[j][i]) > fabs(a[cur][i])) cur = j;
		}
		if (fabs(a[cur][i]) < eps) continue;
		std::swap(a[cur], a[i]);
		for (int j = i + 1; j <= n + 1; ++ j) a[i][j] /= a[i][i];
		a[i][i] = 1.00;
		for (int j = 1; j <= n; ++ j) {
			if (i == j) continue;
			for (int k = i + 1; k <= n + 1; ++ k) a[j][k] -= a[j][i] * a[i][k];
			a[j][i] = 0;
		}
	}
	for (int i = 1; i < n; ++ i) printf("%.3lf ", a[i][n + 1]);
	return 0;
}
```

最后修改：2021 年 09 月 04 日