BZOJ 1013 JSOI2008 球形空间产生器sphere 高斯消元
浏览数：42 /
时间：2015年06月09日
题目大意：给定n维空间下的n+1个点，求这n个点所在的球面的球心
曾经尝试了很久的模拟退火0.0 至今仍未AC 0.0
今天挖粪涂墙怒学了高斯消元……
我们设球心为X(x1,x2,...,xn)
假设有两点A(a1,a2,...,an)和B(b1,b2,...,bn)
那么我们可以得到两个方程
(x1-a1)^2+(x2-a2)^2+...+(xn-an)^2=r^2
(x1-b1)^2+(x2-b2)^2+...+(xn-bn)^2=r^2
这些方程都是二次的，无法套用高斯消元
但是我们可以做一些处理 将上面两个方程相减可得
(a1-b1)x1+(a2-b2)x2+...+(an-bn)xn=[ (a1^2-b1^2)+(a2^2-b2^2)+...+(an^2-bn^2) ]/2
r被消掉，n个方程，n个未知数套用高斯消元模板即可
一直在纠结模拟退火为啥切不掉0.0
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 20
using namespace std;
int n;
double pos[M],a[M][M],ans[M];
int main()
{
int i,j,k;
cin>>n;
for(i=1;i<=n;i++)
scanf("%lf",&pos[i]);
for(i=1;i<=n;i++)
{
double temp[M];
for(j=1;j<=n;j++)
{
scanf("%lf",&temp[j]);
a[i][j]=pos[j]-temp[j];
a[i][n+1]+=pos[j]*pos[j]-temp[j]*temp[j];
}
a[i][n+1]/=2;
}
for(i=1;i<=n;i++)
{
k=0;
for(j=i;j<=n;j++)
if( fabs(a[j][i])>fabs(a[k][i]) )
k=j;
for(j=1;j<=n+1;j++)
swap(a[i][j],a[k][j]);
for(j=i+1;j<=n;j++)
{
double temp=-a[j][i]/a[i][i];
for(k=i;k<=n+1;k++)
a[j][k]+=a[i][k]*temp;
}
}
for(i=n;i;i--)
{
for(j=n;j>i;j--)
a[i][n+1]-=a[i][j]*ans[j];
ans[i]=a[i][n+1]/a[i][i];
}
for(i=1;i<=n;i++)
printf("%.3lf%c",ans[i],i==n?'\n':' ');
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
