Cod sursa(job #799608)

Utilizator ChallengeMurtaza Alexandru Challenge Data 19 octombrie 2012 16:13:33
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cmath>

//#define DEBUG

#ifndef DEBUG
	#define PRINT(x)
	#define D if(0)
#else
	#define PRINT(x) \
		cout<<#x<<":\t"<<x<<endl
	#define D if(1)
#endif

using namespace std;

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

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;
}

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();

	PRINT(N<<" "<<M);

	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)
		{
			++j;
			continue;
		}

PRINT(i<<" "<<j);

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

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

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

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

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

D{
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=M+1;++j)
		{
			cout<<A[i][j]<<" ";
		}
		cout<<"\n";
	}
}

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