Cod sursa(job #2840990)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 29 ianuarie 2022 10:05:24
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
#include <iomanip>
#include <cmath>

using namespace std;

typedef double ld;

const int N = 300 + 7;
int n, m, pi[N], pj[N];
ld a[N][N], sol[N];

int main() {
  freopen ("gauss.in", "r", stdin);
  freopen ("gauss.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m + 1; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		pi[i] = -1;
	}
	for (int j = 1; j <= m; j++) {
		pj[j] = -1;
	}
	while (true) {
		int r = -1, c = -1;
		ld mx = -1;
		for (int i = 1; i <= n; i++) {
			if (pi[i] == -1) {
				for (int j = 1; j <= m; j++) {
					if (pj[j] == -1) {
						ld current = abs(a[i][j]);
						if (current > mx) {
							mx = current;
							r = i;
							c = j;
						}
					}
				}
			}
		}
		if (r == -1 && c == -1) {
			break;
		}
		ld x = a[r][c];
		for (int j = 1; j <= m + 1; j++) {
			a[r][j] /= x;
		}
		pi[r] = c;
		pj[c] = r;
		for (int row = 1; row <= n; row++) {
			if (row != r && abs(a[row][c]) > 1e-14) {
				ld coef = a[row][c] / a[r][c];
				for (int j = 1; j <= m + 1; j++) {
					a[row][j] -= a[r][j] * coef;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (pi[i] != -1) {
			sol[pi[i]] = a[i][m + 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		ld sum = 0;
		for (int j = 1; j <= m; j++) {
			sum += sol[j] * a[i][j];
		}
		if (abs(sum - a[i][m + 1]) > 1e-14) {
			cout << "Imposibil\n";
			return 0;
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << fixed << setprecision(10) << sol[i] << " ";
	}
	cout << "\n";
	return 0;
}