Cod sursa(job #1484472)

Utilizator howsiweiHow Si Wei howsiwei Data 11 septembrie 2015 12:07:46
Problema Algoritmul lui Gauss Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const long double eps = 1e-9;
 
bool iszero(long double x) {
    return abs(x) < eps;
}
 
int main() {
    ios::sync_with_stdio(false);
    freopen("gauss.in", "r", stdin);
    freopen("gauss.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<long double>> a(n, vector<long double>(m+1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m+1; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> head(n, m+1);
	int rd = n;
    for (int i = 0; i < n; i++) {
		bool flag = false;
        for (head[i] = i == 0 ? 0 : head[i-1]+1; head[i] < m+1; head[i]++) {
            for (int j = i; j < n; j++) {
				if (!iszero(a[j][head[i]])) {
					swap(a[i], a[j]);
					flag = true;
					break;
				}
            }
			if (flag) {
				break;
			}
        }
        if (!flag) {
			rd = i;
            break;
        }
        for (int j = head[i]+1; j < m+1; j++) {
            a[i][j] /= a[i][head[i]];
        }
		a[i][head[i]] = 1;
        for (int j = i+1; j < n; j++) {
            for (int k = head[i]+1; k < m+1; k++) {
                a[j][k] -= a[j][head[i]] * a[i][k];
            }
			a[j][head[i]] = 0;
        }
    }
    // for (int i = 0; i < n; i++) {
    //  for (int j = 0; j < m+1; j++) {
    //      printf("%f ", a[i][j]);
    //  }
    //  puts("");
    // }
    // for (int i = 0; i < n; i++) {
    //  printf("%d ", head[i]);
    // }
    // puts("");
    // return 0;
    vector<long double> ans(m);
    for (int i = rd-1; i >= 0; i--) {
		if (head[i] == m) {
			puts("Imposibil");
			return 0;
		}
        ans[head[i]] = a[i][m];
        for (int j = head[i]+1; j < m; j++) {
            ans[head[i]] -= a[i][j]*ans[j];
        }
    }
    for (auto x: ans) {
        printf("%.9Lf ", x);
    }
    puts("");
    return 0;
}