Cod sursa(job #2978455)

Utilizator AlexNeaguAlexandru AlexNeagu Data 13 februarie 2023 19:37:58
Problema Algoritmul lui Gauss Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.04 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;
    vector<int> mapRow(m, -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]) - eps < abs(matrix[i][col])) {
                bestRow = i;
            }
        }
        if(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 = col; i <= m; ++i) {
            swap(matrix[bestRow][i], matrix[row][i]);
        }
        mapRow[col] = row;
        for(int i = 0; i < n; ++i) {
            if(i == row) {
                continue;
            }
            double c = matrix[i][col] / matrix[row][col];
            for(int j = col; j <= m; ++j) {
                matrix[i][j] -= matrix[row][j] * c;
            }
        }
        ++row;
    }
    for(int i = 0; i < m; ++i) {
        if(mapRow[i] != -1) {
            int r = mapRow[i];
            ans[i] = matrix[r][m] / matrix[r][i];
        }
    }
    
    // let's check 
    for(int i = 0; i < n; ++i) {
        double sum = 0;
        for(int j = 0; j < m; ++j) {
            sum += ans[j] * matrix[i][j];
        }
        if(abs(sum - matrix[i][m]) > eps) {
            // solutia nu corespunde --> nu are 
            return 0;
        }
    }
    for(int i = 0; i < m; ++i) {
        if(mapRow[i] == -1) {
            // avem unele elemente pe diag = 0 dar totusi solutia s-o obtinut => o infinitate 
            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;
}