Cod sursa(job #1605574)

Utilizator linia_intaiConstantinescu Iordache Ciobanu Noi cei din linia intai linia_intai Data 19 februarie 2016 10:34:14
Problema Algoritmul lui Gauss Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <bits/stdc++.h>

#define double long double
using namespace std;

const int NMAX = 305;

const double eps = 1e-14l;

class Gauss {
public:
    int n, m;

    double mat[NMAX][NMAX];
    double sol[NMAX];

    void solve(ostream& g) {
        //Elimination
        int vars = 0;
        for (int col = 1; col <= m; ++ col) {
            int lin;
            for (lin = vars + 1; lin <= n; ++ lin)
                if (fabs(mat[lin][col]) >= eps) {
                    schimb(vars + 1, lin);
                    break;
                }

            if (lin == n + 1)
                continue;

            ++ vars;
            prod(vars, 1 / mat[vars][col]);

            for (lin = vars + 1; lin <= n; ++ lin)
                scad(lin, mat[lin][col], vars);
        }

        //"Imposibil"
        for (int lin = vars + 1; lin <= n; ++ lin)
            if (fabs(mat[lin][m + 1]) >= eps) {
                g << "Imposibil\n";
                return ;
            }

        //Back substitution
        for (int lin = vars; lin; -- lin) {
            int pivot = 1;
            for (; pivot <= m; ++ pivot)
                if (fabs(mat[lin][pivot]) >= eps)
                    break;

            sol[pivot] = mat[lin][m + 1];
            for (int col = pivot + 1; col <= m; ++ col)
                sol[pivot] -= mat[lin][col] * sol[col];
        }

        for (int col = 1; col <= m; ++ col)
            g << fixed << setprecision(10) << sol[col] << " \n"[col == m];
    }

private:
    inline void schimb(int lin1, int lin2) {
        for (int i = 1; i <= m + 1; ++ i)
            swap(mat[lin1][i], mat[lin2][i]);
    }

    inline void prod(int lin, double alpha) {
        for (int i = 1; i <= m + 1; ++ i)
            mat[lin][i] *= alpha;
    }

    inline void scad(int lin1, double alpha, int lin2) {
        for (int i = 1; i <= m + 1; ++ i)
            mat[lin1][i] -= alpha * mat[lin2][i];
    }
} g;

istream& operator>>(istream& f, Gauss &g) {
    f >> g.n >> g.m;
    for (int i = 1; i <= g.n; ++ i)
        for (int j = 1; j <= g.m + 1; ++ j)
            f >> g.mat[i][j];

    return f;
}

int main()
{
    ifstream cin("gauss.in");
    ofstream cout("gauss.out");

    cin >> g;

    g.solve(cout);

    cin.close();
    cout.close();
    return 0;
}