首页 > 代码库 > 【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 }
View Code

 

【BZOJ2013】【JSOI2008】球形空间产生器