Cod sursa(job #2799156)

Utilizator vladth11Vlad Haivas vladth11 Data 12 noiembrie 2021 15:54:53
Problema Algoritmul lui Gauss Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 305;
const ll VMAX = 21;
const ll INF = (1LL << 55);
const ll MOD = 998244353;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 30;

const long double eps = 0.000000001;

int n, m;
long double coef[NMAX][NMAX];
long double sol[NMAX];
int r[NMAX];

int main() {
    ifstream cin("gauss.in");
    ofstream cout("gauss.out");
    int i, j;
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m + 1; j++) {
            cin >> coef[i][j];
        }
    }
    int lin = 1;
    for(j = 1; j <= m; j++) {
        int k = lin;
        for(i = lin + 1; i <= n; i++) {
            if(abs(coef[i][j]) > abs(coef[k][j])) {
                k = i;
            }
        }
        if(abs(coef[k][j]) < eps)
            continue;
        r[j] = lin;
        //debug(k);
        for(int t = 1; t <= m + 1; t++) {
            swap(coef[k][t], coef[lin][t]);
        }
        //debug(coef[lin][j]);
        for(i = 1; i <= n; i++) {
            if(i==lin)
                continue;
            long double c = coef[i][j] / coef[lin][j];
            for(int t = j; t <= m + 1; t++) {
                coef[i][t] -= coef[lin][t] * c;
            }
        }
        lin++;
    }
    for(i = 1; i <= m; i++) {
        if(!r[i]) {
            continue;
        }
        sol[i] = coef[r[i]][m + 1] / coef[r[i]][i];
    }
    for(i = n; i >= 1; i--) {
        long double ans = coef[i][m + 1];
        for(j = m; j >= 1; j--) {
            ans -= coef[i][j] * sol[j];
        }
        //debug(ans);
        if(abs(ans) > eps) {
            cout << "Imposibil\n";
            return 0;
        }
    }
    for(i = 1; i <= m; i++) {
        cout << sol[i] << " ";
    }
    return 0;
}