CompetitiveProgramming/codeforces/100923/C.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;

int main()
{
  freopen("bujor.in", "r", stdin);
  freopen("bujor.out", "w", stdout);
  int test, n, used[222];
  double a[222][222], b[222][222];
  cin >> test;
  while (test--)
  {
    cin >> n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
      {
        scanf("%lf", a[i] + j);
        b[i][j] = i == j ? 1 : 0;
      }

    memset(used, -1, sizeof used);
    for (int j = 0; j < n; j++)
    {
      int row = -1;
      double best = EPS;
      for (int i = 0; i < n; i++)
        if (used[i] < 0 && fabs(a[i][j]) > best)
        {
          row = i;
          best = fabs(a[i][j]);
          break;
        }

      if (row < 0) continue;
      used[row] = j;

      for (int i = 0; i < n; i++)
        if (used[i] < 0 && fabs(a[i][j]) > EPS)
        {
          double coef = 1. * a[i][j] / a[row][j];
          for (int jj = j; jj < n; jj++)
            a[i][jj] -= coef * a[row][jj];
          for (int jj = 0; jj < n; jj++)
            b[i][jj] -= coef * b[row][jj];
        }
    }

    for (int j = n - 1; j >= 0; j--)
    {
      int row = -1;
      for (int i = 0; i < n; i++)
        if (used[i] == j)
        {
          row = i;
          break;
        }

      if (row < 0)
        continue;

      double cur = a[row][j];
      for (int jj = 0; jj < n; jj++)
      {
        a[row][jj] /= cur;
        b[row][jj] /= cur;
      }

      for (int i = 0; i < n; i++)
        if (used[i] < j)
        {
          double coef = a[i][j];
          for (int jj = 0; jj <= n; jj++)
          {
            a[i][jj] -= coef * a[row][jj];
            b[i][jj] -= coef * b[row][jj];
          }
        }
    }

    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        printf("%.12lf%c", b[i][j], (j == n - 1 ? '\n' : ' '));
  }
}