[bzoj1013](JSOI2008)球形空间产生器sphere(高斯消元)

 1 /**************************************************************
 2     Problem: 1013
 3     User: AsmDef
 4     Language: C++
 5     Result: Accepted
 6     Time:0 ms
 7     Memory:1272 kb
 8 ****************************************************************/
 9  
10 //Asm_Def
11 #include <iostream>
12 #include <cctype>
13 #include <cstdio>
14 #include <vector>
15 #include <algorithm>
16 #include <cmath>
17 #include <queue>
18 using namespace std;
19 template<typename T>inline void getd(T &x){
20     char c = getchar();
21     bool minus = 0;
22     while(!isdigit(c) && c != ‘-‘)c = getchar();
23     if(c == ‘-‘)minus = 1, c = getchar();
24     x = c - ‘0‘;
25     while(isdigit(c = getchar()))x = x * 10 + c - ‘0‘;
26     if(minus)x = -x;
27 }
28 /*======================================================*/
29 const double eps = 1e-12;
30 double *Eq[11], Ans[11];
31 int N;
32 inline void init(){
33     double a, P[11][12];
34     getd(N);int i, j;
35     for(j = 0;j < N;++j)scanf("%lf", *P + j);
36     for(i = 1;i <= N;++i){
37         for(j = 0;j < N;++j)
38             scanf("%lf", P[i] + j);
39         P[i-1][N] = 0;
40         for(j = 0;j < N;++j){
41             a = P[i-1][j] + P[i][j];
42             P[i-1][j] = P[i][j] - P[i-1][j];
43             P[i-1][N] += a * P[i-1][j] / 2.0;
44         }
45         Eq[i-1] = P[i-1];
46     }
47 }
48 inline void solve(){
49     int i, j, k;
50     double frac;
51     for(i = 0;i < N;++i){
52         for(j = i+1;j < N;++j)
53             if(fabs(Eq[i][i]) < fabs(Eq[j][i]))swap(Eq[i], Eq[j]);
54          
55         if(fabs(Eq[i][i]) < eps){
56             cout << "No Answer" << endl;
57             exit(1);
58         }
59         for(j = i+1;j < N;++j){
60             if(fabs(frac = Eq[j][i] / Eq[i][i]) < eps)continue;
61             Eq[j][i] = 0;
62             for(k = i+1;k <= N;++k)
63                 Eq[j][k] -= frac * Eq[i][k];
64         }
65     }
66     for(i = N-1;i >= 0;--i){
67         Ans[i] = Eq[i][N] / Eq[i][i];
68         for(j = 0;j < i;++j)
69             Eq[j][N] -= Eq[j][i] * Ans[i];
70     }
71     for(i = 0;i < N;++i)
72         printf("%.3lf%c", Ans[i], i == N-1 ? ‘\n‘ : ‘ ‘);
73 }
74 int main(){
75     #if defined DEBUG
76     //freopen("test", "r", stdin);
77     #else
78     //freopen("bzoj_1013.in", "r", stdin);
79     //freopen("bzoj_1013.out", "w", stdout);
80     #endif
81     init();
82     solve();
83      
84     #if defined DEBUG
85     //cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
86     #endif
87     return 0;
88 }