Cod sursa(job #2938592)

Utilizator pregoliStana Andrei pregoli Data 12 noiembrie 2022 12:30:48
Problema Algoritmul lui Gauss Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "text";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");
const char *IMPOSSIBLE_MESSAGE = "Imposibil";
constexpr double EPS = 1e-10;
int nrEqs, nrUnknowns;
vector<vector<double>> eqSystem;

void read() {
    fin >> nrEqs >> nrUnknowns;
    eqSystem.resize(nrEqs, vector<double>(nrUnknowns + 1));
    for (int i = 0; i < nrEqs; i++) {
        for (int j = 0; j <= nrUnknowns; j++) {
            fin >> eqSystem[i][j];
        }
    }
}

bool isNon0(double x) {
    return fabs(x) >= EPS;
}

void toREF() {
    for (int i = 0, j = 0; i < nrEqs && j < nrUnknowns;) {
        int non0RowPos = -1;
        for (int row = i; row < nrEqs; row++) {
            if (isNon0(eqSystem[row][j])) {
                non0RowPos = row;
                break;
            }
        }

        if (non0RowPos == -1) {
            j++;
            continue;
        }

        if (non0RowPos != i) {
            swap(eqSystem[i], eqSystem[non0RowPos]);
        }

        for (int col = j + 1; col <= nrUnknowns; col++) {
            eqSystem[i][col] /= eqSystem[i][j];
        }
        eqSystem[i][j] = 1.0;

        for (int ii = i + 1; ii < nrEqs; ii++) {
            for (int jj = j + 1; jj <= nrUnknowns; jj++) {
                eqSystem[ii][jj] -= eqSystem[ii][j] * eqSystem[i][jj];
            }
            eqSystem[ii][j] = .0;
         }

        i++, j++;
    }
}

vector<double> getSol() {
    vector<double> unknowns(nrUnknowns, .0);
    for (int i = nrEqs - 1; i >= 0; i--) {
        int unknownPos = -1;
        for (int j = 0; j <= nrUnknowns; j++) {
            if (isNon0(eqSystem[i][j])) {
                unknownPos = j;
                break;
            }
        }

        if (unknownPos == -1) {
            continue;
        }

        if (unknownPos == nrUnknowns) {
            return vector<double>();
        }

        unknowns[unknownPos] = eqSystem[i][nrUnknowns];
        for (int j = unknownPos + 1; j < nrUnknowns; j++) {
            unknowns[unknownPos] -= eqSystem[i][j] * unknowns[j];
        }
    }
    return unknowns;
}

void write(const vector<double> &ans) {
    if (ans.empty()) {
        fout << IMPOSSIBLE_MESSAGE;
    } else {
        for (auto it : ans) {
            fout << fixed << setprecision(10) << it << ' ';
        }
    }
    fout << '\n';
    fout.close();
}

int main() {
    read();
    toREF();
    write(getSol());
    return 0;
}