Cod sursa(job #1987256)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 30 mai 2017 00:25:08
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "gauss"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MAXN 310
double *a[MAXN];
double phys[MAXN][MAXN];
int N, M;
double sols[MAXN];

const double eps = 1e-11;

inline bool equals(double x, double y) {
	return fabs(x - y) < eps;
}

void init() {
	for (int i = 0; i < MAXN; ++i)
		a[i] = &phys[i][0];
}

void divideLine(int li, double val, int scol = 0) {
	for (int i = scol; i <= M; ++i)
		a[li][i] /= val;
}

void subMultLine(int to, int from, int scol, double factor) {
	for (int i = scol; i <= M; ++i)
		a[to][i] -= a[from][i] * factor;
}

void printMat() {
	//if(1 == 1) return;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= M; ++j)
			fprintf(stderr, "%c%.2lf ", (a[i][j] < 0) ? '-' : ' ', fabs(a[i][j]));
		fputs("\n", stderr);
	}
	fputs("------------ -------------\n", stderr);
}

int getFirstNonZero(int line) {
	int i;
	for (i = 0; i < M && equals(a[line][i], 0.0); ++i);
	return i;
}

bool solve() {
	int curLine = 0, curCol = 0;
	for (; curLine < N && curCol < M; ) {
		int li = curLine;
		for (; li < N && equals(a[li][curCol], 0.0); ++li);
		if (li >= N) {
			++curCol;
			continue;
		}
		swap(a[li], a[curLine]);
		divideLine(curLine, a[curLine][curCol], curCol);
		for (int j = curLine + 1; j < N; ++j)
			subMultLine(j, curLine, curCol, a[j][curCol]);
		++curLine, ++curCol;
	}
	//printMat();
	for (int i = 0; i < M; ++i)
		sols[i] = 0.0;
	for (int i = curLine - 1; i >= 0; --i) {
		//locate first nonzero element
		int col = getFirstNonZero(i);
		double ans = a[i][M];
		if (col >= M) {
			if (!equals(ans, 0.0))
				return false;
			continue;
		}
		for (int j = M - 1; j > col; --j)
			ans -= a[i][j] * sols[j];
		sols[i] = ans;
	}
	for (int i = curLine; i < N; ++i) {
		double ans = a[i][M];
		for (int j = 0; j < M; ++j)
			ans -= a[i][j] * sols[j];
		if (!equals(ans, 0.0)) return false;
	}

	//if (1 == 1) return true;

	/*for (int i = 0; i < N; ++i) {
		double ans = 0.0;
		for (int j = 0; j < M; ++j)
			ans += a[i][j] * sols[j];
		fprintf(stderr, "%3d : %.10lf\n", i);
	}*/

	return true;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OuFile, "w", stdout));
	init();
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i)
	for (int j = 0; j <= M; ++j)
		scanf("%lf", &a[i][j]);
	if (solve()) {
		for (int i = 0; i < M; ++i)
			printf("%.10lf ", sols[i]);
	}
	else puts("Imposibil");
	return 0;
}