Cod sursa(job #2383399)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 19 martie 2019 13:51:36
Problema Algoritmul lui Gauss Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.52 kb
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define dbg(x) cerr<<#x": "<<(x)<<endl
#define dbg_p(x) cerr<<#x": "<<(x).first<<' '<<(x).second<<endl
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<setw(6)<<(x)[_]<<' ';cerr<<endl;}
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define id(i, j) (c + y + (i - 1) * y + j - 2)

template<typename T1, typename T2>
ostream& operator <<(ostream &out, const pair<T1, T2> &item) {
	out << '(' << item.first << ", " << item.second << ')';
	return out;
}

template<typename T>
ostream& operator <<(ostream &out, const vector<T> &v) {
	for(const auto &item : v) out << item << ' ';
	return out;
}

const int NMAX = 2510;
const double EPS = 1e-10;

bool know[NMAX];
double x[NMAX];
vector<double> v[NMAX];

void print(int m) {
	cerr << ("************************************************************************") << endl;
	for(int i = 0; i < m; ++i) {
		dbg_v(v[i], v[i].size());
	}
	cerr << ("************************************************************************") << endl;
}

bool gauss(int m) {
	int i, j, k, l, row;
	
	for(i = 0, j = 0; i < m && j + 1 < v[0].size(); ++j) {
		// print(m);
		for(row = i, k = i + 1; k < m; ++k) if(abs(v[k][j]) > abs(v[row][j])) row = k;
		// dbg(row);
		if(row != i) v[i].swap(v[row]);
		// if(row != i) {
		// 	for(l = j; l < v[i].size(); ++l) swap(v[i][l], v[row][l]);
		// }
		
		if(abs(v[i][j]) >= EPS) {
			for(k = i + 1; k < m; ++k) {
				if(abs(v[k][j]) < EPS) continue;
				
				double mul = -v[k][j] / v[i][j];
				for(l = j; l < v[k].size(); ++l) v[k][l] += v[i][l] * mul;
			}
			
			++i;
		}
	}
	// print(m);
	
	for(i = m - 1; i >= 0; --i) {
		for(j = 0; j < v[i].size() && abs(v[i][j]) < EPS; ++j);
		if(j == int(v[i].size()) - 1) return false;
		if(j == int(v[i].size())) continue;
		
		x[j] = v[i].back();
		for(l = j + 1; l + 1 < v[i].size(); ++l) x[j] -= v[i][l] * x[l];
		x[j] /= v[i][j];
	}
	
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	freopen("gauss.in", "r", stdin);
	freopen("gauss.out", "w", stdout);
	
	int i, j, k, y, c, q, nrVar, nrEq;
	double r, p;
	
	cin >> nrEq >> nrVar;
	++nrVar;
	
	for(i = 0; i < nrEq; ++i) {
		v[i].resize(nrVar);
		for(j = 0; j < nrVar; ++j) cin >> v[i][j];
	}
	
	if(gauss(nrEq)) {
		for(j = 0; j + 1 < nrVar; ++j) cout << fixed << setprecision(12) << x[j] << ' ';
		cout << '\n';
	} else {
		cout << "Imposibil\n";
	}
	
	
	// dbg("OK");
	
	return 0;
}