Cod sursa(job #2921867)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 2 septembrie 2022 00:59:17
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>
#include <iomanip>

using namespace std;

const double eps = 1e-10;

bool eq(double a, double b) {
    return max(a, b) - min(a, b) < eps;
}

vector<double> solve(int N, int M, vector<vector<double> >& A) {
    int i = 0, j = 0;
    while (i < N && j < M) {
        for (int l = i; l < N; l++)
            if (!eq(A[l][j], 0)) {
                A[l].swap(A[i]);
                break;
            }
        if (eq(A[i][j], 0)) {
            ++j;
            continue;
        }
        
        for (int c = M; c >= j; c--)
            A[i][c] /= A[i][j];
        
        for (int l = i + 1; l < N; l++)
            for (int c = M; c >= j; c--)
                A[l][c] -= A[l][j] * A[i][c];
        
        i++;
        j++;
    }

    /*
    for (i = 0; i < N; i++) {
        for (j = 0; j <= M; j++)
            cout << A[i][j] << ' ';
        cout << '\n';
    }
    */

    vector<double> x(M, 0.0);

    for (i = N - 1; i >= 0; i--) {
        for (j = 0; j < M && eq(A[i][j], 0.0); ++j);
        //cout << i << ' ' << j << '\n';

        double r = A[i][M];
        for (int c = j + 1; c < M; c++)
            r -= A[i][c] * x[c];
        
        if (j < M) {
            x[j] = r / A[i][j];
            continue;
        }

        if (!eq(r, 0))
            return vector<double>();
    }

    return x;
}

int main() {
    ifstream f("gauss.in");
    ofstream g("gauss.out");

    int N, M;
    f >> N >> M;

    vector<vector<double> > A(N, vector<double>(M + 1));

    for (int i = 0; i < N; i++)
        for (int j = 0; j <= M; j++)
            f >> A[i][j];
    

    vector<double> sol = solve(N, M, A);

    if (sol.empty()) {
        g << "Imposibil";
    } else {
        for (double x : sol)
            g << fixed << setprecision(8) << x << ' ';
    }
    g << '\n';


    f.close();
    g.close();
    return 0;
}