Cod sursa(job #665035)

Utilizator ChallengeMurtaza Alexandru Challenge Data 21 ianuarie 2012 14:46:40
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <iomanip>

using namespace std;

const char InFile[]="gauss.in";
const char OutFile[]="gauss.out";
const int MaxN=302;
const double EPS=1e-8;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M;
double A[MaxN][MaxN],SOL[MaxN];

inline double myabs(const double a)
{
	if(a<0)
	{
		return -a;
	}
	return a;
}

inline bool equal(const double a, const double b)
{
	return myabs(a-b)<EPS;
}

inline void Gauss()
{
	int i=1,j=1;
	while(i<=N && j<=M)
	{
		int k=i;
		for(;k<=N;++k)
		{
			if(!equal(A[k][j],0))
			{
				break;
			}
		}

		if(k==N+1)
		{
			++i;
			continue;
		}

		if(k!=i)
		{
			for(int t=1;t<=M+1;++t)
			{
				swap(A[i][t],A[k][t]);
			}
		}

		for(int u=j+1;u<=M+1;++u)
		{
			A[i][u]/=A[i][j];
		}
		A[i][j]=1.0;

		for(int t=i+1;t<=N;++t)
		{
			for(int u=j+1;u<=M+1;++u)
			{
				A[t][u]-=A[t][j]*A[i][u];
			}
			A[t][j]=0;
		}

		++i;
		++j;
	}

	for(i=N;i>0;--i)
	{
		for(j=1;j<=M+1;++j)
		{
			if(!equal(A[i][j],0))
			{
				if(j==M+1)
				{
					SOL[0]=-1;
					return;
				}

				SOL[j]=A[i][M+1];
				for(int k=j+1;k<=M;++k)
				{
					SOL[j]-=SOL[k]*A[i][k];
				}
				break;
			}
		}
	}
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M+1;++j)
		{
			fin>>A[i][j];
		}
	}
	fin.close();

	Gauss();

	if(SOL[0]==-1)
	{
		fout<<"Imposibil";
	}
	else
	{
		fout<<std::fixed<<std::setprecision(10);
		for(register int i=1;i<=M;++i)
		{
			fout<<SOL[i]<<" ";
		}
	}
	fout.close();
	return 0;
}