Cod sursa(job #2749818)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 mai 2021 13:42:08
Problema Algoritmul lui Gauss Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <bits/stdc++.h>

#define llg     long long


template <typename type>
type modulus(type a) { return std::max(a, -a); }

class GaussCalculator {
public:
    static int run(std::vector <std::vector<double>> a, std::vector <double> &ans) {
        const double EPS = 1e-9;
        int n = (int) a.size();
        int m = (int) a[0].size() - 1;

        std::vector <int> where(m, -1);
        for (int col=0, row=0; col<m && row<n; ++col) {
            int sel = row;
            for (int i=row; i<n; ++i)
                if (modulus(a[i][col]) > modulus(a[sel][col]))
                    sel = i;
            if (modulus(a[sel][col]) < EPS)
                continue;
            for (int i=col; i<=m; ++i)
                std::swap(a[sel][i], a[row][i]);
            where[col] = row;

            for (int i=0; i<n; ++i)
                if (i != row) {
                    double c = a[i][col] / a[row][col];
                    for (int j=col; j<=m; ++j)
                        a[i][j] -= a[row][j] * c;
                }
            ++ row;
        }

        ans.assign(m, 0);
        for (int i=0; i<m; ++i)
            if (where[i] != -1)
                ans[i] = a[where[i]][m] / a[where[i]][i];
        for (int i=0; i<n; ++i) {
            double sum = 0;
            for (int j=0; j<m; ++j)
                sum += ans[j] * a[i][j];
            if (modulus(sum - a[i][m]) > EPS)
                return 0;
        }

        for (int i=0; i<m; ++i)
            if (where[i] == -1)
                return 2;
        return 1;
    }
};


int32_t main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::ifstream input ("gauss.in");
    std::ofstream output("gauss.out");

    int N, M;   input >> N >> M;
    std::vector <std::vector <double>> a(N);
    for (auto &it:a) {
        it.resize(M+1);
        for (auto &x:it) input >> x;
    }

    std::vector <double> ans;
    auto ret = GaussCalculator::run(a, ans);
    if (ret != 1) output << "Imposibil\n";
    else {
        for (auto &x : ans) output << std::fixed << std::setprecision(8) << x << ' ';
    }

    return 0;
}