首页 > 代码库 > 【BZOJ2013】【JSOI2008】球形空间产生器
【BZOJ2013】【JSOI2008】球形空间产生器
看chty代码
原题:
BZOJ挂了……等好了补上题面
设圆心的坐标为(x,y,z……),给的第一个个点的坐标为(a,b,c……)
然后这个点到圆心的距离就可以表示出来:(a-x)^2+(b-y)^2+(c-z)^2+……=a^2-2ax+x^2+b^2-2by+y^2+……
然后又给了n个点,假设某个点坐标为(a‘,b‘,c‘……)
两个点到圆心的距离相等:a^2-2ax+x^2+b^2-2by+y^2+……=a‘^2-2a‘x+x^2+b‘^2-2b‘y+y^2+……
把不含未知数的都移到一边,剩下的移到另一边:2(a‘-a)x+2(b‘-b)y+2(c‘-c)z+……=a‘^2-a^2+b‘^2-b^2+c‘^2-c^2……
然后根据第一个点和接下来的n个点就可以构造出n个方程
然后就可以开心地用高斯消元解掉辣(然而我高斯消元的模板还没理解+背会)
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 double eps=1e-6; 8 int n; 9 double b[11],a[11][11];10 void gauss(){11 int now=1;12 for(int i=1;i<=n;i++){13 int temp=now;14 while(temp<=n && !(fabs(a[temp][i])>eps)) temp++;15 if(temp>n) continue;16 if(temp!=now)17 for(int j=1;j<=n+1;j++)18 swap(a[temp][j],a[now][j]);19 double c=a[now][i];20 for(int j=1;j<=n+1;j++) a[now][j]/=c;21 for(int j=1;j<=n;j++)if(j!=now){22 c=a[j][i];23 for(int k=1;k<=n+1;k++)24 a[j][k]-=c*a[now][k];25 }26 now++;27 }28 }29 int main(){30 //freopen("ddd.in","r",stdin);31 freopen("bzoj_1013.in","r",stdin);32 freopen("bzoj_1013.out","w",stdout);33 cin>>n;34 double _left;35 for(int i=1;i<=n;i++) cin>>b[i];36 for(int i=1;i<=n;i++)37 for(int j=1;j<=n;j++){38 scanf("%lf",&_left);39 a[i][j]=2*(_left-b[j]);40 a[i][n+1]+=_left*_left-b[j]*b[j];41 }42 gauss();43 for(int i=1;i<=n;i++) printf("%.3lf ",a[i][n+1]);44 cout<<endl;45 return 0;46 }
【BZOJ2013】【JSOI2008】球形空间产生器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。