Pagini recente » Cod sursa (job #2328299) | Cod sursa (job #2232645) | Cod sursa (job #2409620) | Cod sursa (job #624762) | Cod sursa (job #2978455)
#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;
}