Pagini recente » Cod sursa (job #1602805) | Cod sursa (job #1232571) | Cod sursa (job #1315595) | Cod sursa (job #504548) | Cod sursa (job #2978581)
#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;
}