Cod sursa(job #2978581)

Utilizator AlexNeaguAlexandru AlexNeagu Data 13 februarie 2023 21:58:12
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.17 kb
#include<bits/stdc++.h>
// #define int long long
#define f first
#define s second
using namespace std;

typedef long long ll;
const int MOD = 1e9 + 9;
const int inf = 1e9;
const double eps = 1e-9;
const double PI = acos(-1);

ifstream in("gauss.in");
ofstream out("gauss.out");
#define cin in 
#define cout out 

int n, m;
vector<vector<double>> matrix;

int solve(vector<vector<double>> &matrix, vector<double> &ans) {
    // matrix - matricea sistemului 
    // in ans se pune solutia 
    // se returneaza 0 - nu are solutie, 1 - o singura solutie, 2 - o infinitate 
    int n = matrix.size(), m = matrix[0].size() - 1;
    // Fiecare coloana - mapata cu un rand. Ideal, mapRow[i] = i. Daca ramane -1, inseamna ca nu e independent.
    int row = 0;
    for(int col = 0; col < m; ++col) {
        // toate coloanele pana acum au fost facute 0 pe randul curent row 
        int bestRow = row;
        for(int i = row; i < n; ++i) {
            if(abs(matrix[bestRow][col]) < abs(matrix[i][col])) {
                bestRow = i;
            }
        }
        if(bestRow >= n || abs(matrix[bestRow][col]) < eps) {
            // nu am gasit nici un rand diferit de 0 pe coloana asta, deci nu e independent
            // totusi, nu terminam algoritmul, poate sunt o infinitate de solutii 
            continue;
        }
        for(int i = 0; i <= m; ++i) {
            swap(matrix[bestRow][i], matrix[row][i]);
        }
        
        // impart toata linia la matrix[row][col]
        for(int i = col + 1; i <= m; ++i) {
            matrix[row][i] = matrix[row][i] / matrix[row][col];
        }
        matrix[row][col] = 1.0;

        for(int i = row + 1; i < n; ++i) {
            for(int j = col + 1; j <= m; ++j) {
                matrix[i][j] -= matrix[i][col] * matrix[row][j];
            }
            matrix[i][col] = 0.0;
        }
        ++row;
    }

    bool infty = false;

    for(int i = n - 1; i >= 0; --i) {
        bool found = false;
        for(int j = 0; j <= m && !found; ++j) {
            if(abs(matrix[i][j]) > eps) {
                if(j == m) {
                    // toate celelalte sunt 0 ==> caz imposibil
                    return 0;
                }
                ans[j] = matrix[i][m];
                for(int k = j + 1; k < m; ++k) {
                    ans[j] -= ans[k] * matrix[i][k];
                }
                found = true;
            }
        }
        // linie full de 0 => avem o infinitate de solutii
        if(!found) {
            infty = true;
        }
    }
    if(infty) {
        return 2;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    matrix.resize(n);
    for(int i = 0; i < n; ++i) {
        matrix[i].resize(m + 1);
        for(int j = 0; j <= m; ++j) {
            cin >> matrix[i][j];
        }
    }

    vector<double> ans(m, 0);

    int verdict = solve(matrix, ans);
    if(verdict > 0) {
        for(auto it: ans) {
            cout << fixed << setprecision(10) << it << ' ';
        }
        cout << '\n';
    }
    else {
        cout << "Imposibil\n";
    }

    return 0;
}