Cod sursa(job #1750279)

Utilizator retrogradLucian Bicsi retrograd Data 29 august 2016 20:57:32
Problema Algoritmul lui Gauss Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;

const double kEps = 1e-12;

namespace Gauss {
	// Transforms a matrix into its row echelon form
	// Returns a vector of pivots (for each variable)
	// or -1 if free variable
	// The bool returns true if system has solution
	pair<bool, vector<int>> ToRowEchelon(vector<vector<double>> &M) {
		int cons = M.size();
		int vars = M[0].size() - 1;

		vector<int> pivot(vars, -1);

		int cur = 0;
		for(int var = 0; var < vars; ++var) {
			if(cur >= cons) continue;

			if(abs(M[cur][var] < kEps)) {
				for(int con = cur + 1; con < cons; ++con) {
					if(M[con][var] != 0) {
						swap(M[con], M[cur]);
						break;
					}
				}
			}

			if(abs(M[cur][var]) > kEps) {
				pivot[var] = cur;
				double aux = M[cur][var];

				for(int i = 0; i <= vars; ++i)
					M[cur][i] /= aux;

				for(int con = 0; con < cons; ++con) {
					if(con != cur) {
						double mul = M[con][var];
						for(int i = 0; i <= vars; ++i) {
							M[con][i] -= mul * M[cur][i];
						}

						assert(M[con][var] < kEps);
					}	
				}

				++cur;
			}
		}

		bool ret = true;
		for(int con = cur; con < cons; ++con)
			if(M[con][vars] > kEps)
				ret = false;

		return make_pair(ret, pivot);
	}  
};

int main() {
	freopen("gauss.in", "r", stdin);
	freopen("gauss.out", "w", stdout);

	int n, m;
	cin >> n >> m;

	vector<vector<double>> M(n, vector<double>(m + 1));
	for(int i = 0; i < n; ++i)
		for(int j = 0; j <= m; ++j)
			cin >> M[i][j];

	auto res = Gauss::ToRowEchelon(M);

	if(res.first == false) {
		cout << "Imposibil" << endl;
		return 0;
	}

	cout << fixed << setprecision(12);
	for(int i = 0; i < m; ++i) {
		if(res.second[i] == -1) {
			cout << 0 << " ";
		} else {
			cout << M[res.second[i]][m] << " ";
		}
	}
	cout << endl;

	return 0;
}