球形空间产生器
显然,这题需要用到高斯消元
但是,直接用的话会发现方程组不仅超过了n个,而且还是非线性的
因此我们需要转化为线性方程来解
设球心坐标为mi,球面上的点坐标为rij,球的半径为k
那么,显然有Σ(rij-mi)²=k²
我们令第一行分别减去2~n+1行,再整理一下,可以得到
Σ2(rij-r0j)mi=Σ(rij²-r0j²)
我们就得到线性方程组了
代码如下:
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<double>>b(n + 1, vector<double>(n + 1));
for (int i = 0;i <= n;i++) for (int j = 1;j <=n;j++) cin >> b[i][j];
vector<vector<double>>a(n + 1, vector<double>(n + 2,0));
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
a[i][j] =2 * (b[i][j] - b[0][j]);
a[i][n+1] += b[i][j] * b[i][j] - b[0][j] * b[0][j];
}
}
for (int i = 1;i <= n;i++) {
int max = i;
for (int j = i + 1;j <= n;j++) if (fabs(a[j][i] > fabs(a[max][i]))) max = j;
for (int j = 1;j <= n + 1;j++) swap(a[i][j], a[max][j]);
for (int j = n + 1;j >= 1;j--) a[i][j] = a[i][j] / a[i][i];
for (int j = 1;j <= n;j++) {
if (j != i) {
double temp = a[j][i] / a[i][i];
for (int k = 1;k <= n + 1;k++) a[j][k] -= a[i][k] * temp;
}
}
}
for (int i = 1;i <= n;i++) cout << fixed << setprecision(3) << a[i][n + 1] << " ";
}
时间复杂度:O(n³)
空间复杂度:O(n²)