[JSOI2008]球形空间产生器

注意到给出N + 1个坐标应该想到压缩方程转化为n个消去一个变元

sigma (x²) +sigma (y²) - sigma (2xy) = R²

sigma (x_i²) +sigma (y_i²) - sigma (2x_iy_i) = R²

相减

下面给出的是gauss-jordan消去法稍有不同

View Code

 1 #include <cstdio>
 2 #include <cmath>
 3 #define sqr(x) x * x
 4 const int N =300;
 5 int n;
 6 double t[N][N], a[N][N], b[N];
 7 int cho[N];
 8 inline void gauss ()
 9 {
10     for (int i = 1; i <= n; i ++)
11     {
12         double t1 (0);int t2 (0);
13         for (int j = 1; j <= n; j ++)
14             if (fabs (a[i][j]) > t1)
15                 t1 = fabs (a[i][j]), t2 = j;cho[t2] = i;
16         
17         double t = a[i][t2];
18         for (int j = 1; j <= n; j ++)
19             a[i][j] /= t;
20         b[i] /= t;
21         
22         for (int j = 1; j <= n; j ++)
23             if (j != i)
24             {
25                 double t = a[j][t2];
26                 for (int k = 1; k <= n; k ++)
27                     a[j][k] -= a[i][k] * t;
28                 b[j] -= b[i] * t;
29             }
30     }
31     for (int i = 1; i <= n; i ++)
32         printf ("%.3lf ", -b[cho[i]] / a[cho[i]][i]);
33 }
34 int main ()
35 {
36     scanf ("%d", &n);
37     for (int i = 1; i <= n + 1; i ++)
38         for (int j = 1; j <= n; j ++)
39             scanf ("%lf", &t[i][j]);
40     for (int i = 2; i <= n + 1; i ++)
41         for (int j = 1; j <= n; j ++)
42             a[i - 1][j] = 2 * (t[1][j] - t[i][j]), b[i - 1] += sqr (t[i][j]) - sqr (t[1][j]);
43     gauss ();
44     return 0;
45 }