【高斯消元】bzoj1013 [JSOI2008]球形空间产生器sphere
浏览数：26 /
时间：2015年06月09日
求圆神饶恕~>_<
根据半径相等的关系建立n+1个二次方程，
然后每个和前一个相减消去二次项，get n个线性方程。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 11
int n;
double B[N][N+1],A[N][N+1],x[N],b[N],pl[N+1][N];
double sqr(double x){return x*x;}
void guass_jordan()
{
memcpy(B,A,sizeof(A));
for(int i=1;i<=n;++i)
B[i][n+1]=b[i];
for(int i=1;i<=n;++i)//枚举:正在消除第i个未知数,之后第i个方程废掉,矩阵行、列-1
{
int pivot=i;
for(int j=i+1;j<=n;++j)//枚举j:把正在处理的未知数的系数的绝对值最大的方程换到第i行
if(fabs(B[j][i])>fabs(B[pivot][i]))
pivot=j;
swap(B[i],B[pivot]);
//if(fabs(B[i][i])<EPS)
//若所有(最大)的该未知数系数为0,说明少一个未知数,有无穷多解
for(int j=i+1;j<=n+1;++j)
B[i][j]/=B[i][i];
for(int j=1;j<=n;++j)
if(i!=j)//枚举所有的方程,从第j个方程中消去第i个未知数
for(int k=i+1;k<=n+1;++k)//依次把第j个方程中的第k个未知数减去应减的数值
B[j][k]-=B[j][i]*B[i][k];
}
for(int i=1;i<=n;++i) x[i]=B[i][n+1];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n+1;++i)
{
for(int j=1;j<=n;++j)
scanf("%lf",&pl[i][j]);
if(i>1)
for(int j=1;j<=n;++j)
{
b[i-1]+=sqr(pl[i-1][j])-sqr(pl[i][j]);
A[i-1][j]=2.0*pl[i-1][j]-2.0*pl[i][j];
}
}
guass_jordan();
for(int i=1;i<n;++i)
printf("%.3f ",x[i]);
printf("%.3f\n",x[n]);
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
