Cod sursa(job #3121391)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 12 aprilie 2023 14:33:19
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb


#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

vector<ld> gauss(int n, int m, vector<vector<ld>> a) {
  const ld eps = 1e-14;
  assert((int)a.size() == n);
  for (int i = 0; i < n; i++) {
    assert((int)a[i].size() == m + 1);
  }
  vector<int> pi(n, -1), pj(m, -1);
  while (1) {
    int r = -1, c = -1;
    vector<int> Is, Js;
    for (int i = 0; i < n; i++) {
      if (pi[i] == -1) {
        Is.push_back(i);
      }
    }
    for (int j = 0; j < n; j++) {
      if (pj[j] == -1) {
        Js.push_back(j);
      }
    }
    for (auto& i : Is) {
      for (auto& j : Js) {
        if ((r == -1 && c == -1) || (abs(a[i][j]) > abs(a[r][c]))) {
          r = i;
          c = j;
        }
      }
    }
    if (r == -1 && c == -1) {
      break;
    }
    if (abs(a[r][c]) < eps) {
      break;
    }
    pi[r] = c;
    pj[c] = r;
    ld multiply = (ld)1 / a[r][c];
    for (int j = 0; j <= m; j++) {
      a[r][j] *= multiply;
    }
    for (int i = 0; i < n; i++) {
      if (i != r && abs(a[i][c]) > eps) {
        ld coef = a[i][c];
        for (int j = 0; j <= m; j++) {
          a[i][j] -= coef * a[r][j];
        }
      }
    }
  }
  vector<ld> sol(m, 0);
  for (int i = 0; i < n; i++) {
    if (pi[i] != -1) {
      sol[pi[i]] = a[i][m];
    }
  }
  for (int i = 0; i < n; i++) {
    ld sum = 0;
    for (int j = 0; j < m; j++) {
      sum += a[i][j] * sol[j];
    }
    if (abs(sum - a[i][m]) > eps) {
      return {};
    }
  }
  return sol;
}

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

  int n, m;
  cin >> n >> m;
  vector<vector<ld>> a(n, vector<ld>(m + 1));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= m; j++) {
      cin >> a[i][j];
    }
  }
  vector<ld> sol = gauss(n, m, a);
  if (sol.empty()) {
    cout << "Imposibil\n";
  }
  else {
    for (auto& x : sol) {
      cout << fixed << setprecision(10) << x << " ";
    }
    cout << "\n";
  }
}