Cod sursa(job #1712796)

Utilizator echipa_BoSSilorUNIBUC Harsan Bicsi Baltatu echipa_BoSSilor Data 3 iunie 2016 18:35:25
Problema Algoritmul lui Gauss Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
/*************************************************************\
~*********************ENJOY THE SILENCE***********************~
\*************************************************************/

#include <bits/stdc++.h>
using namespace std;

/*******************Debugging defines*************************/

#define ok_dump() cerr<<"OK\n"
#define var_dump(x) cerr<<#x": "<<x<<'\n'
#define arr_dump(x, n) {cerr<<#x"[]: ";\
	for(int _=1;_<=n;++_) cerr<<x[_]<<" ";cerr<<'\n';}

/*************************************************************/

bool equals(double x, double y) {
	return abs(x - y) < 1e-9;
}

template<typename T>
struct Gauss {
	using Row = vector<T>;
	using Matrix = vector<Row>;


	void add(Row &A, Row &B, T mul) {
		// A += B * mul
		for(int i = 0; i < A.size(); ++i)
			A[i] += B[i] * mul;
	}

	bool ToRowEchelon(Matrix &M) {
		int rows = M.size(),
			cols = M[0].size();

		int now_row = 0;

		for(int col = 0; col < cols - 1; ++col) {

			if(equals(M[now_row][col], 0)) {
				for(int row = now_row + 1; row < rows; ++row) {
					if(!equals(M[row][col], 0)) {
						swap(M[now_row], M[row]);
						break;
					}
				}
			}

			if(!equals(M[now_row][col], 0)) {
				auto val = M[now_row][col];
				for(int i = 0; i < cols; ++i)
					M[now_row][i] /= val;

				for(int i = 0; i < rows; ++i) {
					if(i != now_row) {
						add(M[i], M[now_row], -M[i][col]);
						assert(M[i][col] == 0);
					}
				}

				now_row += 1;
				if(now_row == rows)
					return true;
			}
		}

		return false;
	}
};


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

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	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];
	
	Gauss<double> gauss;
	if(!gauss.ToRowEchelon(M)) {
		cout << "Imposibil\n";
		return 0;
	}

	cout << fixed << setprecision(12);

	int rows = M.size(),
		cols = M[0].size();

	int cur_row = 0;
	for(int col = 0; col < cols - 1; ++col) {
		if(cur_row < rows && !equals(M[cur_row][col], 0)) {
			cout << M[cur_row][cols - 1] << " ";
			++cur_row;
		} else {
			cout << 0 << " ";
		}
	}



	return 0;
}

/*************************************************************\
~*********************ENJOY THE SILENCE***********************~
\*************************************************************/