Cod sursa(job #2906660)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 26 mai 2022 22:54:00
Problema Algoritmul lui Gauss Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.92 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using data = double;

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

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

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

    bool solved_by(const vector<data>& sol) {
        assert(coef.size() == sol.size());

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

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

ecuatie operator*(data 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<data> 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 < ecs; i++) { // pentru fiecare coloana
            for(int j = i; j < ecs; j++) {
                if(i < ecuatii[j].coef.size() && abs(ecuatii[j].coef[i]) > EPS) {
                    // swap(ecuatii[i], ecuatii[j]);
                    auto tmp = ecuatii[i];
                    ecuatii[i] = ecuatii[j];
                    ecuatii[j] = tmp;

                    break;
                }
            }

            if(ecuatii[i].coef.size() <= i || 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 = ecs - 1; i >= 0; i--) {
            for(int oi = i - 1; oi >= 0; oi--) {
                if(i < ecuatii[oi].coef.size()) ecuatii[oi] = ecuatii[oi] + (-ecuatii[oi].coef[i]) * ecuatii[i];
            }

            if(i < solution.size()) 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;
}