Cod sursa(job #1987221)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 29 mai 2017 23:10:32
Problema Algoritmul lui Gauss Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 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-9;

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 multiplyLine(int li, double val, int scol = 0) {
	for (int i = scol; i <= M; ++i)
		a[li][i] *= val;
}

void subtractLine(int to, int from, int scol = 0) {
	for (int i = scol; i <= M; ++i)
		a[to][i] -= a[from][i];
}

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

bool solve() {
	printMat();
	for (int i = 0; i < min(N, M); ++i) {
		int li = i;
		for (; li < min(N, M) && equals(a[li][i], 0.0); ++li);
		if (li >= min(N, M)) continue;
		swap(a[li], a[i]);
		for (int j = i + 1; j < min(N, M); ++j) {
			if (equals(a[j][i], 0.0)) continue;
			multiplyLine(j, a[i][i] / a[j][i], i);
			subtractLine(j, i, i);
		}
	}
	printMat();
	for (int i = 0; i < M; ++i)
		sols[i] = 0.0;
	for (int i = min(N, M) - 1; i >= 0; --i) {
		if (equals(a[i][i], 0.0)) continue;
		double ans = a[i][M];
		for (int j = M - 1; j > i; --j)
			ans -= a[i][j] * sols[j];
		if (equals(a[i][i], 0.0)) {
			if (!equals(ans, 0.0))
				return false;
			continue;
		}
		sols[i] = ans / a[i][i];
	}
	for (int i = min(N, M); 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;
	}
	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;
}