Cod sursa(job #2734263)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 31 martie 2021 16:48:10
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

ifstream in ("gauss.in");
ofstream out ("gauss.out");

const int INF = 2e9;
const int N = 300;
const double EPS = 1e-10;

double a[1 + N][1 + N];
double v[1 + N];
int n, m;

void Gauss() {
  int i, j, k;
  for(j = 1, i = 1; j <= m && i <= n; i++, j++) {
    // cautam o linie k pt care A[k][j] != 0 si A[k][j] maxim
    k = i;
    for(int maxline = i; maxline <= n; maxline++)
      if(abs(a[maxline][j]) > abs(a[k][j]))
        k = maxline;

    if(abs(a[k][j]) < EPS) // coloana nula, sarim peste
      continue;

    // interschimbam liniile i si k
    for(int col = 1; col <= m + 1; col++)
      swap(a[k][col], a[i][col]);

    // impartim toate valorile de pe linia i la a[i][j]
    for(int col = j + 1; col <= m + 1; ++col)
      a[i][col] = a[i][col] / a[i][j];
    a[i][j] = 1;

    // anulam celelalte valori folosindu-ne de pivot
    for(k = i + 1; k <= n; k++) {
      for(int col = j + 1; col <= m + 1; col++)
        a[k][col] = a[k][col] - a[k][j] * a[i][col];
      a[k][j] = 0;
    }
  }

  for(i = n; i >= 1; i--)
    for(j = 1; j <= m + 1; j++)
      if(abs(a[i][j]) > EPS) {
        if(j == m + 1) {
          out << "Imposibil\n";
          exit(0);
        }
        
        // aflam necunoscutele
        v[j] = a[i][m + 1];
        for(k = j + 1; k <= m; k++)
          v[j] = v[j] - v[k] * a[i][k];
        
        j = m + 1;
      }
}

int main() {
  in >> n >> m;
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m + 1; j++)
      in >> a[i][j];

  Gauss();

  out << fixed << setprecision(10);
  for(int i = 1; i <= m; i++)
    out << v[i] << " ";
  in.close();
  out.close();
  return 0;
}