【高斯消元】BZOJ 1013: [JSOI2008]球形空间产生器sphere

Description

　　有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。

Input

　　第一行是一个整数，n。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。

Output

　　有且只有一行，依次给出球心的n维坐标（n个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

　　模板题。。

　　一开始还听说卡精度什么的。。还要什么最大公倍数什么的，还要最大行什么的。。完全不会啊QAQ。。

　　然后我坚持打裸的。。

　　思想:我们先来考虑二维。。(X-x₁)²+(Y-y₁)²=(X-x₂)²+(Y-y₂)²

　　让我们化简开来。。

　　首先X²与Y²可以抵消。

　　然后就是喜闻乐见的弄来弄去啦。。

　　然后就是。。变成了2X(x2-x1)+2Y(y2-y1)=x₂²-x₁²+y₂²-y₁²

　　之后就可以拓展成n维辣。。

　　之后就是喜闻乐见的Gauss消元辣。。

　　我用的是把矩阵变成三角形。。

　　一交。

　　PE？什么gui错误？

　　听说最后要加\n？

　　好吧，再交一次吧。。

　　WA?好吧，printf开在外面没.3lf。

　　继续。

　　RE?　好吧，我不吝啬空间了。

　　继续。喜闻乐见的A了？

　　真是神题，卡精度还卡格式- -

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 double f[][],ga[][],ans[];

 int n;

 void Solve()

 {

     for(int i=n;i>=;i--)

     {

         ans[i]=ga[i][n+];

         for(int j=i+;j<=n;j++)

             ans[i]-=ans[j]*ga[i][j];

         ans[i]/=ga[i][i];

     }

 }

 void Guass()

 {

     for(int i=;i<=n;i++)//枚举处理的个数

         for(int j=i;j<=n;j++)//方程的第几个

         {

             double gg=ga[j][i-]/ga[i-][i-];

             for(int k=i;k<=n+;k++)//方程的几个未知项

                 ga[j][k]=gg*ga[i-][k]-ga[j][k];

         }

     Solve();

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n+;i++)

         for(int j=;j<=n;j++)

             scanf("%lf",&f[i][j]);

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             ga[i][j]=(f[i+][j]-f[i][j])*,ga[i][n+]+=f[i+][j]*f[i+][j]-f[i][j]*f[i][j];

     Guass();

     for(int i=;i<n;i++)

         printf("%.3lf ",ans[i]);

     printf("%.3lf\n",ans[n]);

     return ;

 }

　　关于高斯消元，我机房神人ysp写了一篇通俗易懂的blog: http://www.cnblogs.com/Robert-Yuan/p/4621481.html

巴特西

【高斯消元】BZOJ 1013: [JSOI2008]球形空间产生器sphere

Description

Input

Output

最新文章

热门文章