这里是题目的传送门
题目的大意是比较好懂的，就是说给你一个(N + 1)个N维空间上的点，让你求这个(N + 1）个点的圆心坐标。
拿到这道题目我首先想到的是模拟退火。。。
为什么？ 不为什么
但是感觉这个正确率可能出现问题，因为这个题并不是求极值，所以只能通过其它的方法来判断是否最优（比如说算标准差什么的，但是这样子真的不太靠谱）
又想到了我之前写过一道模拟退火的题目，调了emmm20次吧，于是就没敢写。
这道题目里有一个性质——即圆心的性质
圆心到每一个点的距离都相同，于是我们可以这样子假设
假设答案为(x1,x2,x3,……,xn),当前这个点为(a1,a2,a3……,an),下一点为(b1,b2,b3……,bn)
我们可以列出方程
(a1 - x1) ^ 2 + (a2 - x2) ^ 2 + (a3 - x3) ^ 2 +……+(an - xn) ^ 2 = (b1 - x1) ^ 2 + (b2 - x2) ^ 2 + …… + (an - xn) ^ 2
化简可得
2(a1 - b1) x1 + 2 (a2 - b2)x2 + …… +2(an - bn)xn=a1 ^ 2 + a2 ^ 2 +……+an ^ 2 - b1 ^ 2 - b2 ^ 2 - …… - bn ^ 2
我们一共有N + 1个点
所以我们可以列出N个方程
接下来就使用高斯消元
把所有的未知数解出来，由于数据保证有解，所以不会存在自由元
大家可以大胆地去做啦
1 #include <cmath> 2 #include <ctime> 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 #define ll long long 8 #define db double 9 #define fo(i,x,y) for (int i=x; i<=y; i++)10 #define pr(i,x,y) for (int i=x; i>=y; i--)11 #define cl(a,x) ??memset(a,x,sizeof(a))12 13 using namespace std;14 15 int N;16 db Mat[15][15];17 db a[15][15];18 19 int main()20 {21 ????scanf("%d",&N);22 ????cl(Mat,0);23 ????fo(i,1,N + 1)24 ????{25 ????????fo(j,1,N)26 ????????{27 ????????????scanf("%lf",&a[i][j]);28 ????????????if (i != 1)29 ????????????{30 ????????????????Mat[i - 1][j]=2 * (a[i][j] - a[i - 1][j]);31 ????????????????Mat[i - 1][N + 1]+=a[i][j] * a[i][j] - a[i - 1][j] * a[i - 1][j];32 ????????????}33 ????????}34 ????}35 ????fo(i,1,N)36 ????{37 ????????int T=i;38 ????????fo(j,i + 1,N)39 ????????{40 ????????????if (fabs(Mat[j][i]) > fabs(Mat[T][i]))41 ????????????{42 ????????????????T=j;43 ????????????}44 ????????}45 ????????if (T != i)46 ????????{47 ????????????fo(j,1,N + 1)48 ????????????{49 ????????????????swap(Mat[i][j],Mat[T][j]);50 ????????????}51 ????????}52 ????????fo(j,i + 1,N)53 ????????{54 ????????????db X=Mat[j][i] / Mat[i][i];55 ????????????fo(k,i,N + 1)56 ????????????{57 ????????????????Mat[j][k]-=Mat[i][k] * X;58 ????????????}59 ????????}60 ????}61 ????pr(i,N,1)62 ????{63 ????????fo(j,i + 1,N)64 ????????{65 ????????????Mat[i][N + 1]-=Mat[j][N + 1] * Mat[i][j];66 ????????}67 ????????Mat[i][N + 1]/=Mat[i][i];68 ????}69 ????fo(i,1,N - 1)70 ????{71 ????????printf("%.3f ",Mat[i][N + 1]);72 ????}73 ????printf("%.3f\n",Mat[N][N + 1]);74 ????return 0;75 }BZOJ 1013 ?[JSOI2008]球形空间产生器sphere
原文地址：https://www.cnblogs.com/TUncleWangT/p/8445449.html