首页 > 代码库 > BZOJ 1013 JSOI2008 球形空间产生器sphere 高斯消元
BZOJ 1013 JSOI2008 球形空间产生器sphere 高斯消元
题目大意:给定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':' '); }
BZOJ 1013 JSOI2008 球形空间产生器sphere 高斯消元
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。