Cod sursa(job #2638433)

Utilizator segtreapMihnea Andreescu segtreap Data 28 iulie 2020 11:11:46
Problema Algoritmul lui Gauss Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
  freopen ("gauss.in", "r", stdin);
  freopen ("gauss.out", "w", stdout);

  typedef long double ld;
  const ld EPS = 1e-14;

  int n, m;
  cin >> n >> m;
  vector<vector<ld>> a(n, vector<ld> (m + 1));
  vector<ld> sol(m, 0);
  vector<int> pr(n, -1), pc(m, -1);

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= m; j++) {
      cin >> a[i][j];
    }
  }

  while (1) {
    ld mx = EPS;
    int r = -1, c = -1;
    for (int i = 0; i < n; i++) {
      if (pr[i] != -1) {
        continue;
      }
      for (int j = 0; j < m; j++) {
        if (pc[j] != -1) {
          continue;
        }
        if (fabs(a[i][j]) > mx) {
          mx = fabs(a[i][j]);
          r = i;
          c = j;
        }
      }
    }
    if (r == -1) {
      break;
    }
    pr[r] = c;
    pc[c] = r;
    ld coef = a[r][c];
    for (int j = 0; j <= m; j++) {
      a[r][j] /= coef;
    }
    for (int i = 0; i < n; i++) {
      if (i != r) {
        ld coef = -a[i][c] / a[r][c];
        for (int j = 0; j <= m; j++) {
          a[i][j] += coef * a[r][j];
        }
      }
    }
  }

  for (int j = 0; j < m; j++) {
    if (pc[j] != -1) {
      sol[j] = a[pc[j]][m];
    }
  }
  for (int i = 0; i < n; i++) {
    ld sum = 0;
    for (int j = 0; j < m; j++) {
      sum += sol[j] * a[i][j];
    }
    if (fabs(sum - a[i][m]) > EPS) {
      cout << "Imposibil\n";
      return 0;
    }
  }
  for (int j = 0; j < m; j++) {
    cout << fixed << setprecision(10) << sol[j] << " ";
  }
  cout << "\n";

  return 0;
}