【bzoj1013】[JSOI2008]球形空间产生器sphere（高斯消元）

1013: [JSOI2008]球形空间产生器sphere

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 4013 Solved: 2119
[Submit][Status][Discuss]
Description

　　有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在&＃xff0c;你被困在了这个n维球体中&＃xff0c;你只知道球
面上n&＃43;1个点的坐标&＃xff0c;你需要以最快的速度确定这个n维球体的球心坐标&＃xff0c;以便于摧毁这个球形空间产生器。

Input

　　第一行是一个整数n(1<&＃61;N&＃61;10)。接下来的n&＃43;1行&＃xff0c;每行有n个实数&＃xff0c;表示球面上一点的n维坐标。每一个实数精确到小数点
后6位&＃xff0c;且其绝对值都不超过20000。

Output

　　有且只有一行&＃xff0c;依次给出球心的n维坐标&＃xff08;n个实数&＃xff09;&＃xff0c;两个实数之间用一个空格隔开。每个实数精确到小数点
后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

Sample Input

2

0.0 0.0

-1.0 1.0

1.0 0.0
Sample Output

0.500 1.500
HINT

　　提示&＃xff1a;给出两个定义&＃xff1a;1、 球心&＃xff1a;到球面上任意一点距离都相等的点。2、 距离&＃xff1a;设两个n为空间上的点A, B

的坐标为(a1, a2, …, an), (b1, b2, …, bn)&＃xff0c;则AB的距离定义为&＃xff1a;dist &＃61; sqrt( (a1-b1)^2 &＃43; (a2-b2)^2 &＃43;

… &＃43; (an-bn)^2 )

Source

**【题解】【高斯消元的模板题 &＃xff08;高斯消元见博文&＃xff1a;
http://blog.csdn.net/reverie_mjp/article/details/51227822&＃xff09;】**
【不过有一点要注意&＃xff0c;因为刚开始时是二次方程组&＃xff0c;所以不能直接高斯消元&＃xff0c;把所有的式子展开&＃xff0c;然后分别于第一个式子相减就可以得到一次方程&＃xff0c;就可以用高斯消元了】
(x1−x)2&＃43;(y1−y)2&＃43;(z1−z)2&＃61;r2
(x2−x)2&＃43;(y2−y)2&＃43;(z2−z)2&＃61;r2
(x3−x)2&＃43;(y3−y)2&＃43;(z3−z)2&＃61;r2
……
展开得&＃xff1a;
x12&＃43;y12&＃43;z12&＃43;x2&＃43;y2&＃43;z2&＃61;2x1x&＃43;2y1&＃xfeff;y&＃43;2z1z
x22&＃43;y22&＃43;z22&＃43;x2&＃43;y2&＃43;z2&＃61;2x2x&＃43;2y2&＃xfeff;y&＃43;2z2z
x32&＃43;y32&＃43;z32&＃43;x2&＃43;y2&＃43;z2&＃61;2x3x&＃43;2y3&＃xfeff;y&＃43;2z3z
……

#include
#include
#include
#include
#define INF 1e-6
using namespace std;
double f[110],a[110][110];
int n;
bool guess()
{int i,j,now&＃61;1;//now表示处理到第几行了 double t;for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i)//枚举未知量的系数 {for(j&＃61;now;j<&＃61;n;&＃43;&＃43;j)if(fabs(a[j][i])>INF) break;//当前未知量系数不为零 if(j>n) continue;if(j!&＃61;now)for(int k&＃61;1;k<&＃61;n&＃43;1;&＃43;&＃43;k) swap(a[j][k],a[now][k]);t&＃61;a[now][i];for(int k&＃61;1;k<&＃61;n&＃43;1;&＃43;&＃43;k) a[now][k]/&＃61;t;for(int k&＃61;1;k<&＃61;n;&＃43;&＃43;k)//手动模拟高斯消元 if(k!&＃61;now){t&＃61;a[k][i];for(int l&＃61;1;l<&＃61;n&＃43;1;&＃43;&＃43;l)a[k][l]-&＃61;t*a[now][l];} now&＃43;&＃43;;}for(i&＃61;now;i<&＃61;n;&＃43;&＃43;i)if(fabs(a[i][n&＃43;1])>INF) return 0;return 1;
}
int main()
{int i,j;scanf("%d",&n);for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i) scanf("%lf",&f[i]);//单独读入第一组数&＃xff0c;为后面去除二次项做准备 for(i&＃61;1;i<&＃61;n;&＃43;&＃43;i)for(j&＃61;1;j<&＃61;n;&＃43;&＃43;j){double x;scanf("%lf",&x);a[i][j]&＃61;2*(x-f[j]);a[i][n&＃43;1]&＃43;&＃61;x*x-f[j]*f[j];}//构造初始矩阵 int k&＃61;guess();for(i&＃61;1;iprintf("%.3lf ",a[i][n&＃43;1]);printf("%.3lf\n",a[n][n&＃43;1]);return 0;
}