Cod sursa(job #2906656)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 26 mai 2022 22:38:25
Problema Algoritmul lui Gauss Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.59 kb
#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-6;
const int precision = 10;

struct ecuatie {
    vector<double> coef;
    double rez;

    ecuatie(int _sz) { coef.resize(_sz, 0); rez = 0; }

    bool solved_by(const vector<double>& sol) {
        if(coef.size() != sol.size()) return false;

        double sum = 0;
        for(int i = 0; i < coef.size(); i++) sum += coef[i] * sol[i];

        return abs<double>(sum - rez) < EPS;
    }
};

ecuatie operator*(double num, const ecuatie& oth) {
    ecuatie ret(oth.coef.size());

    for(int i = 0; i < ret.coef.size(); i++) {
        ret.coef[i] = oth.coef[i] * num;
    }
    ret.rez = oth.rez * num;

    return ret;
}

ecuatie operator+(const ecuatie& a, const ecuatie& b) {
    assert(a.coef.size() == b.coef.size());

    ecuatie ret(a.coef.size());

    for(int i = 0; i < ret.coef.size(); i++) {
        ret.coef[i] = a.coef[i] + b.coef[i];
    }
    ret.rez = a.rez + b.rez;

    return ret;
}

istream& operator>> (istream& stream, ecuatie& e) {
    for(auto &c : e.coef) stream >> c;
    stream >> e.rez;
    return stream;
}

ostream& operator<< (ostream& stream, const ecuatie& e) {
    for(auto c : e.coef) stream << fixed << setprecision(precision) << c << " ";
    stream << fixed << setprecision(precision) << e.rez;

    return stream;
}

struct sistem {
    vector<ecuatie> ecuatii;
    vector<double> solution;

    sistem(int _n, int _m) {
        ecuatii.resize(_n, ecuatie(_m));
        solution.resize(_m, 0);
    }

    bool solved() {
        bool ret = true;
        for(auto &e : ecuatii) {
            ret &= e.solved_by(solution);
            if(!ret) return false;
        }
        return ret;
    }

    void simplify() {
        const int vars = ecuatii[0].coef.size(); // numarul de necunoscute
        const int ecs = ecuatii.size(); // numarul de ecuatii

        // Top to Bottom
        for(int i = 0; i < vars; i++) { // pentru fiecare coloana
            for(int j = i; j < ecs; j++) {
                if(abs(ecuatii[j].coef[i]) > EPS) { swap(ecuatii[i], ecuatii[j]); break; }
            }
            if(abs(ecuatii[i].coef[i]) < EPS) {
                #ifdef LIBERE
                    cerr << "Variabila " << i << " este libera!" << endl;
                #endif // LIBERE

                continue;
            }

            ecuatii[i] = (1. / ecuatii[i].coef[i]) * ecuatii[i];

            for(int oi = i + 1; oi < ecs; oi++) {
                ecuatii[oi] = ecuatii[oi] + (-ecuatii[oi].coef[i]) * ecuatii[i];
            }
        }

        // Bottom to Top
        for(int i = vars - 1; i >= 0; i--) {
            for(int oi = i - 1; oi >= 0; oi--) {
                ecuatii[oi] = ecuatii[oi] + (-ecuatii[oi].coef[i]) * ecuatii[i];
            }

            solution[i] = ecuatii[i].rez;
        }
    }
};

istream& operator>> (istream& stream, sistem& s) {
    for(auto &e : s.ecuatii) stream >> e;
    return stream;
}

ostream& operator<< (ostream& stream, const sistem& s) {
    stream << s.ecuatii.size() << " " << s.ecuatii[0].coef.size() << '\n';
    for(auto &e : s.ecuatii) stream << e << '\n';

    return stream;
}

#ifndef LOCAL

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

#define cin in
#define cout out

#endif // LOCAL

int main()
{
    int n, m; cin >> n >> m;
    sistem s(n, m); cin >> s;

    s.simplify();

    if(s.solved() == false) cout << "Imposibil" << '\n';
    else { for(auto sol : s.solution) cout << fixed << setprecision(precision) << sol << " "; }

    return 0;
}