【解析】代數(shù)變形+高斯消元

[分析]
依據(jù)題目以下的提示。設(shè)x[i][j]表示第i個點在第j維的坐標(biāo)。r[j]為圓心在第j維的坐標(biāo)
能夠知道：
dis=根號(∑(x[i][j]-r[j])^2)。
因為平方的非負(fù)性。所以能夠推出 dis^2=∑(x[i][j]-r[j])^2。
依據(jù)平方和公式，(x[i][j]-r[j])^2=r[j]^2+x[i][j]^2-2*x[i][j]*r[j]。
∴dis^2=∑r[j]^2+∑x[i][j]^2-∑2*x[i][j]*r[j]。
依據(jù)n+1個坐標(biāo)，能夠用i和i+1兩個坐標(biāo)列出等量條件：
∑r[j]^2+∑x[i][j]^2-∑2*x[i][j]*r[j]=∑r[j]^2+∑x[i+1][j]^2-∑2*x[i+1][j]*r[j]。
把∑r[j]^2消去。參數(shù)放在右邊，未知數(shù)放在左邊。
化簡易得：
∑(x[i+1][j]-x[i][j])*r[j]=(∑x[i+1][j]^2-∑x[i][j]^2)/2。
如今變成了一元n次的方程組，能夠直接使用高斯消元求解。
對于∑x[i+1][j]^2，能夠所有提前預(yù)處理出來。這樣會快一點。

[代碼]

因為準(zhǔn)備要睡覺了沒心機(jī)檢查，結(jié)果重新AC，手感真好...

#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std;const int N=15; const double eps=1e-5;int n; double x[N][N]; double a[N][N],sum[N],res[N];void init(void) {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+1;i++)for (int j=1;j<=n;j++)sum[i]+=x[i][j]*x[i][j];for (int i=1;i<=n;i++){for (int j=1;j<=n;j++)a[i][j]=x[i+1][j]-x[i][j];a[i][n+1]=(sum[i+1]-sum[i])/2;} }inline int cmp(double i,double j) {if (fabs(i-j)<eps) return 0;return i<j?-1:1; }inline void swap(int i,int j) {for (int k=1;k<=n+1;k++) a[i][k]+=a[j][k];for (int k=1;k<=n+1;k++) a[j][k]=a[i][k]-a[j][k];for (int k=1;k<=n+1;k++) a[i][k]-=a[j][k]; }void gauss(void) {double r;for (int i=1;i<=n;i++){for (int j=i+1;j<=n;j++)if (!cmp(a[i][i],0)||cmp(abs(a[i][i]),abs(a[j][i]))>0) swap(i,j);for (int j=i+1;j<=n;j++)if (cmp(a[i][j],0)){r=a[j][i]/a[i][i];for (int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*r;}}for (int i=n;i;i--){for (int j=i+1;j<=n;j++) a[i][n+1]-=a[i][j]*res[j];res[i]=a[i][n+1]/a[i][i];}for (int i=1;i<n;i++) printf("%0.3lf ",res[i]);printf("%0.3lf\n",res[n]); }int main(void) {init();gauss(); return 0; }
【小結(jié)】
①理清思路再開始寫，理清思路要把自己不知道怎么寫的問題先想好。
②為了保證自己算法的正確性（盡管一般都是正確的），要套幾個小樣例去驗證。

轉(zhuǎn)載于:https://www.cnblogs.com/jzdwajue/p/7297543.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ】1013 球形空间产生器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。