BZOJ 1013 球形空间产生器

我们考虑每一个点到球心点距离相等。

然后，将第一个点的方程和其他点的方程作差，然后裸高斯消元即可。

注意精度。（这题倒是不卡精度）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct point
{
double x[15];
}p[15];
double table[15][15];
int n;
double ans[15];
void modify(int x)
{
double regis[15];
int rec;
for (int i=x+1;i<=n;i++)
{
if (table[i][x]!=0)
{
rec=i;
for (int j=1;j<=n+1;j++)
regis[j]=table[i][j];
break;
}
}
for (int i=1;i<=n+1;i++)
{
table[rec][i]=table[x][i];
table[x][i]=regis[i];
}
}
void Gauss()
{
for (int i=1;i<=n;i++)
{
if (table[i][i]==0)
modify(i);
if (table[i][i]!=1)
{
for (int j=i+1;j<=n+1;j++)
table[i][j]=table[i][j]/table[i][i];
table[i][i]=1;
}
for (int j=i+1;j<=n;j++)
{
double r=table[j][i]/(-table[i][i]);
for (int k=i+1;k<=n+1;k++)
table[j][k]=table[j][k]+r*(table[i][k]);
table[j][i]=0;
}
}
for (int i=n;i>=1;i--)
{
ans[i]=table[i][n+1];
for (int j=i-1;j>=1;j--)
table[j][n+1]=table[j][n+1]-table[j][i]*ans[i];
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n+1;i++)
for (int j=1;j<=n;j++)
scanf("%lf",&p[i].x[j]);
for (int i=2;i<=n+1;i++)
{
for (int j=1;j<=n;j++)
table[i-1][j]=2*(p[i].x[j]-p[1].x[j]);
for (int j=1;j<=n;j++)
table[i-1][n+1]=table[i-1][n+1]+p[i].x[j]*p[i].x[j]-p[1].x[j]*p[1].x[j];
}
Gauss();
for (int i=1;i<=n-1;i++)
printf("%.3lf ",ans[i]);
printf("%.3lf",ans[n]);
return 0;
}

BZOJ 1013 球形空间产生器

原文：http://www.cnblogs.com/ziliuziliu/p/5223505.html