Cod sursa(job #2774579)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 12 septembrie 2021 00:29:35
Problema Algoritmul lui Gauss Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <bits/stdc++.h>
using namespace std;

void setIO(string name, bool input = true, bool output = true){
  string inputname = name + ".in";
  string outputname = name + ".out";
  if(input) freopen(inputname.c_str(), "r", stdin);
  if(output) freopen(outputname.c_str(), "w", stdout);
}

int n;
int m;

bool solve(vector<vector<long double>> &a, vector<long double> &b, vector<long double> &x){
  for(int i = 0; i < min(n, m); i++){
    int best = -1;
    for(int j = i; j < min(n, m); j++){
      if(fabs(a[i][j]) < 1e-10) continue;
      if(best == -1 or fabs(a[j][i]) > fabs(a[best][i])) best = j;
    }
    if(best == -1) continue;
    if(best != i){
      for(int j = 0; j < m; j++) swap(a[i][j], a[best][j]);
      swap(b[i], b[best]);
    }
    for(int j = i + 1; j < n; j++){
      long double coef = a[j][i] / a[i][i];
      b[j] -= coef * b[i];
      for(int k = 0; k < m; k++){
        a[j][k] -= coef * a[i][k];
      }
    }
  }
  vector<bool> vis(m, false);
  for(int i = n - 1; i >= 0; i--){
    int at = 0;
    while(at < m and (fabs(a[i][at]) < 1e-10) or vis[at]) at++;
    if(at == m) continue;
    long double val = b[i];
    for(int j = 0; j < m; j++){
      if(j == at) continue;
      val -= x[j] * a[i][j];
    }
    x[at] = val / a[i][at];
    vis[at] = true;
  }
  for(int i = 0; i < n; i++){
    long double sum = 0;
    for(int j = 0; j < m; j++){
      sum += a[i][j] * x[j];
    }
    if(fabs(sum - b[i]) > 1e-10) return false;
  }
  return true;
}

int main(){
  setIO("gauss");
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  vector<long double> b(n);
  vector<vector<long double>> a(n, vector<long double>(m));
  for(int i = 0; i < n; i++){
    for(int j = 0; j <= m; j++){
      if(j == m) cin >> b[i];
      else cin >> a[i][j];
    }
  }
  vector<long double> x(m, 0);
  if(not solve(a, b, x)){
    cout << "Imposibil" << endl;
    return 0;
  }
  for(int i = 0; i < m; i++){
    cout << setprecision(8) << fixed << x[i] << " \n"[i + 1 == m];
  }
  return 0;
}