当前位置: 代码迷 >> 综合 >> 【BZOJ1096】球形空间产生器
  详细解决方案

【BZOJ1096】球形空间产生器

热度:98   发布时间:2024-01-13 09:50:50.0

题解:
设球心为 (x1,x2,,xn) ,按照每个点到球心距离相等列出方程组,直接求解即可

//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int inf=(1<<30);
const double eps=1e-12;
int n,m;
double f[110][110],ans[110];
inline int in()
{char ch=getchar();int f=1,tmp=0;while(ch<'0'||ch>'9') {
   if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}return tmp*f;
}
inline int gi(double x)
{if(x>=-eps&&x<=eps) return 0;return x>0?1:-1;
}
double a[110][110];bool gauss()
{for(int i=1;i<=n;i++){int num=i;for(int j=i+1;j<=n;j++)if(gi(fabs(f[j][i])-fabs(f[num][i])))num=i;if(num!=i)for(int j=1;j<=n+1;j++)swap(f[num][j],f[i][j]);for(int j=i+1;j<=n;j++)if(gi(f[i][i])){double t=f[j][i]/f[i][i];for(int k=i;k<=n+1;k++) f[j][k]-=f[i][k]*t;}}for(int i=n;i>=1;i--){if(gi(f[i][i])==0) return 0;for(int j=i+1;j<=n;j++) f[i][n+1]-=f[i][j]*ans[j];ans[i]=f[i][n+1]/f[i][i];}return 1;
}int main()
{n=in();for(int i=1;i<=n+1;i++)for(int j=1;j<=n;j++){scanf("%lf",&a[i][j]);if(i>1){f[i-1][j]=(a[i][j]-a[i-1][j])*2.0;f[i-1][n+1]+=a[i][j]*a[i][j]-a[i-1][j]*a[i-1][j];}}gauss();for(int i=1;i<n;i++) printf("%.3lf ",ans[i]);printf("%.3lf",ans[n]);return 0;
}