Cod sursa(job #1201797)

Utilizator andreioneaAndrei Onea andreionea Data 26 iunie 2014 01:04:59
Problema Algoritmul lui Gauss Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 kb
#include <fstream>
#include <iomanip>

#define INFILE "gauss.in"
#define OUTFILE "gauss.out"

#define MAXN 300
#define MAXM 301

float A[MAXN][MAXM], X[MAXM - 1];
int N, M;

using std::ifstream;
using std::ofstream;
inline void swap_lines(int l1, int l2)
{
	for (auto j = 0; j <= M; ++j)
		std::swap(A[l1][j], A[l2][j]);
}
inline bool linearly_independent(int line)
{
	if (line == 0)
		return true;
	for (auto other_line = 0; other_line < line; ++other_line) {
		auto column = 0;
		while (column <= M && (A[other_line][column] == 0.0f || A[line][column]))
			++column;
		if (column == M + 1)
			continue;
		float factor = A[other_line][column] / A[line][column];
		while (column <= M && A[other_line][column] != 0.0f && A[line][column] != 0.0f && A[other_line][column] / A[line][column] == factor)
			++column;
		if (column == M + 1)
			return false;
	}
	for (auto i = 0; i < line && i < M; ++i) {
		if (A[line][i] == 0.0f)
			continue;
		if (A[i][i] == 0.0f) {
			if (A[line][i] != 0.0f)
				swap_lines(i, line);
			break;
		}
		float factor = A[line][i] / A[i][i];
		for (auto j = i; j <= M; ++j) {
			A[line][j] -= A[i][j] * factor;
		}
	}
	return true;
}

int main()
{
	ifstream fin(INFILE);
	ofstream fout(OUTFILE);
	fin >> N >> M;
	int last_line = 0;
	for (auto i = 0; i < N; ++i){
		bool null_coeffs = true;
		bool null_res = true;
		for (auto j = 0; j <= M; ++j){
			fin >> A[last_line][j];
			if (A[last_line][j] != 0.0f)
				if (j < M)
					null_coeffs = false;
				else
					null_res = false;
		}
		if (null_coeffs && !null_res) {
			fin.close();
			fout << "Imposibil";
			fout.close();
			return 0;
		}
		if (linearly_independent(last_line))
			++last_line;
	}
	fin.close();
	fout << std::setprecision(10);
	while (last_line >= M) {
		if (A[last_line][M - 1] == 0.0f && A[last_line][M] != 0.0f) {
			fout << "Imposibil";
			fout.close();
			return 0;
		}
		--last_line;
	}
	for (auto i = last_line + 1; i < M; ++i) {
		X[i] = 0.0f;
	}
	while (last_line >= 0) {
		auto sum = 0.0f;
		for (auto j = last_line + 1; j < M; ++j)
			sum += A[last_line][j] * X[j];
		if (A[last_line][last_line] == 0.0f)
			if (sum != A[last_line][M]){
				fout << "Imposibil";
				fout.close();
				return 0;
			}
			else
				X[last_line] = 0.0f;
		else
			X[last_line] = (A[last_line][M] - sum) / A[last_line][last_line];
		--last_line;
	}
	for (auto i = 0; i < M; ++i)
		fout << X[i] << " ";
	fout.close();
	return 0;
}