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

[JSOI2008]球形空间产生器sphere

省选难度的板子 + 普及思维 = 紫题（没毛病

日推天天推紫题再见了同学们我自请退群

为什么要我一个三维生物想象n维空间呢

以二维举例（糊一波我的手稿qwq反正只有我自己看quq

x0, y0 ☞ 球心坐标

通过距离公式以及已知量和未知量可以构造出n元一次方程组

后一个式子减去前一个式子

每一个未知量的系数都是 2*（这一个点的坐标 - 下一个点的该坐标）

等式右边就是该点坐标平方 - 下一个点坐标平方，每一维加起来（这里每一维的意思大概是，几维坐标就有几个啊啊啊啊说不清楚看代码qwq

然后高斯消元！

我luoluo的啥我也不清楚，反正纪念一下我做的为数不多的紫题吧QAQ

 1 /**************************************************************
 2     Problem: 1013
 3     User: Hwjia
 4     Language: C++
 5     Result: Accepted
 6     Time:12 ms
 7     Memory:1296 kb
 8 ****************************************************************/
 9  
10 #include<cmath>
11 #include<cstdio>
12 #include<iostream>
13 using namespace std;
14 const int sz = 20;
15 int n;
16 double num[sz][sz], plat[sz][sz], ans[sz];
17 double eps = 1e-7;
18 void build_matrix() {
19     for(int i = 2; i <= n+1; i++) {
20         for(int j = 1; j <= n; j++) {
21             plat[i-1][j] = 2*(num[i-1][j]-num[i][j]);
22             plat[i-1][n+1] += (num[i-1][j]*num[i-1][j] - num[i][j]*num[i][j]);
23         }
24     }
25 /*  for(int i = 1; i <= n; i++) {
26         for(int j = 1; j <= n+1; j++) {
27             printf("%.3lf ", plat[i][j]);
28         }
29         cout<<endl;
30     }*/
31 }
32 void Guass() {
33     for(int i = 1; i <= n; i++) {
34         int flag = i;
35         for(int j = i+1; j <= n; j++) {
36             if(fabs(plat[flag][i]) < fabs(plat[j][i])) 
37                 flag = j;
38         }
39         if(flag != i) swap(plat[i], plat[flag]);
40         double div = plat[i][i];
41         for(int j = i; j <= n+1; j++)
42             plat[i][j] /= div;
43         for(int j = i+1; j <= n; j++) {
44             div = plat[j][i];
45             for(int k = i; k <= n+1; k++) 
46                 plat[j][k] -= (plat[i][k]*div);
47         }
48     }
49     ans[n] = plat[n][n+1];
50     for(int i = n-1; i >= 1; i--) {
51         ans[i] = plat[i][n+1];
52         for(int j = i+1; j <= n; j++) 
53             ans[i] -= (plat[i][j] * ans[j]);
54     }
55 }
56 int main() {
57     scanf("%d", &n);
58     for(int i = 1; i <= n+1; i++)
59         for(int j = 1; j <= n; j++)
60             scanf("%lf", &num[i][j]);
61     build_matrix(); 
62     Guass();
63     for(int i = 1; i <= n; i++)
64         printf("%.3lf ", ans[i]);
65     return 0;
66 }

这个题显然他就很神奇，在洛咕34ms，去bzoj交64ms，去掉注释80ms，加上注释又交了一发， 12ms了？？？？

看来以后注释不能随便去掉

评测机会觉得你是认真的宝宝会跑的更快哦qwq

对惹， div是关键字，以后不能用！！！用pivot代替；

div（int, int）将两个数相除，返回商和余数，包含在<cstdlib>库中

又一次，完结撒不动花QAQ