Cod sursa(job #2847419)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 10 februarie 2022 19:40:04
Problema Algoritmul lui Gauss Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;
#ifdef INFOARENA
ifstream fin("gauss.in");
ofstream fout("gauss.out");
#else
ifstream fin("ciorna.in");
ofstream fout("ciorna.out");
#endif // INFOARENA
using ld = long double;
const ld eps = 1e-14;
vector <ld> gaussian(vector <vector <ld>> a) {
    int n = a.size(), m = a[0].size() - 1;
    vector <ld> sol(m, 0);
    int curr = 0;
    vector <int> last(n, -1);
    for(int l = 0; l < m; l++) {
        int best = curr;
        for(int i = curr + 1; i < n; i++)
            if(abs(a[i][l]) > abs(a[best][l]))
                best = i;
        if(abs(a[best][l]) < eps) continue;
        last[curr] = l;
        swap(a[curr], a[best]);
        ld div = a[curr][l];
        for(int i = l; i <= m; i++)
            a[curr][i] /= div;
        for(int i = curr + 1; i < n; i++) {
            ld sub = a[i][l];
            for(int j = l; j <= m; j++)
                a[i][j] -= a[curr][j] * sub;
        }
        curr++;
    }
    for(int i = 0; i < n; i++) {
        bool ok = true;
        for(int j = 0; j < m; j++)
            ok &= abs(a[i][j]) < eps;
        if(ok && abs(a[i][m]) < eps)
            return {};
    }
    for(int i = n - 1; i >= 0; i--) {
        sol[last[i]] = a[i][m];
        for(int j = m - 1; j > last[i]; j--)
            sol[last[i]] -= sol[j] * a[i][j];
    }
    return sol;
}

int main()
{
    int n, m;
    fin >> n >> m;
    vector <vector <ld>> a(n);
    for(int i = 0; i < n ; i++) {
        a[i].resize(m + 1);
        for(int j = 0; j <= m; j++)
            fin >> a[i][j];
    }
    vector <ld> sol = gaussian(a);
    if(!sol.size()) return !bool(fout << "Imposibil");
    fout << fixed << setprecision(10);
    for(ld x : sol)
        fout << x << " ";
    return 0;
}