Cod sursa(job #1113368)

Utilizator deividFlorentin Dumitru deivid Data 20 februarie 2014 16:02:40
Problema Algoritmul lui Gauss Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include<stdio.h>
#include<algorithm>
#include<cassert>

#define maxdim 305
#define directions 4

using namespace std;

int vars,eqs;
double P[directions][maxdim][maxdim];
double a[maxdim][maxdim],sol[maxdim];

const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
const double err = 1e-11;

inline bool equal ( const double &x , const double &y ){
	return x-y < err && y-x < err;
}

inline void gauss () {
	
	int i = 1,j = 1;
	while ( i <= eqs && j <= vars ){
		
		int found = 0;
		for ( int k = i ; k <= eqs ; ++k ){
			if ( !equal(a[k][j],0.0) ){
				found = k; break ;
			}
		}
		
		if ( !found ){ ++j; continue ; }
		
		for ( int k = j ; k <= vars+1 ; ++k ){
			swap(a[i][k],a[found][k]);
		}
		
		for ( int variable = j+1 ; variable <= vars+1 ; ++variable ){
			a[i][variable] /= a[i][j];
		}
		a[i][j] = 1;
		
		for ( int equation = i+1 ; equation <= eqs ; ++equation ){
			if ( equal(a[equation][j],0.0) )	continue ;
			
			for ( int variable = j+1 ; variable <= vars+1 ; ++variable ){
				a[equation][variable] -= a[i][variable]*a[equation][j];
			}
			a[equation][j] = 0;
		}
		
		++i; ++j;
	}
}

inline void getSolutions () {
	
	for ( int i = eqs ; i >= 1 ; --i ){
		
		int j = 1;
		while ( j <= vars+1 && equal(a[i][j],0.0) )	++j;
		
		if ( j == vars+1 )	assert(false);
		if ( j == vars+2 )	continue ;
		
		sol[j] = a[i][vars+1];
		for ( int k = j+1 ; k <= vars ; ++k ){
			sol[j] -= sol[k]*a[i][k];
		}
	}
}

int main () {
	
	#ifndef ONLINE_JUDGE
	freopen("firstknight.in","r",stdin);
	freopen("firstknight.out","w",stdout);
	#endif
	
	for ( ; ; ){
		
		scanf("%d %d",&vars,&eqs);
//		if ( n == 0 && m == 0 )	break ;
		
		for ( int i = 1 ; i <= eqs ; ++i ){
			for ( int j = 1 ; j <= vars+1 ; ++j ){
				scanf("%lf",&a[i][j]);
			}
		}
		
//		vars = eqs = n*m;
//		for ( int i = 1 ; i <= n ; ++i ){
//			for ( int j = 1 ; j <= m ; ++j ){
//				
//				int now = getCode(i,j);
//				a[now][now] = 1; a[now][vars+1] = (i != n || j != m) ? 1 : 0;
//				
//				for ( int d = 0 ; d < directions ; ++d ){
//					int iv = i+dx[d],jv = j+dy[d];
//					
//					if ( iv < 1 || iv > n || jv < 1 || jv > m )	continue ;
//					
//					int neighbour = getCode(iv,jv);
//					a[now][neighbour] = -P[d][i][j];
//				}
//			}
//		}
		
		gauss();
		getSolutions();
		
		for ( int i = 1 ; i <= vars ; ++i ){
			printf("%.10lf ",sol[i]);
		}
		printf("\n");
		
		for ( int i = 1 ; i <= eqs ; ++i ){
			for ( int j = 1 ; j <= vars+1 ; ++j ){
				a[i][j] = 0;
			}
			sol[i] = 0;
		}
		
		break ;
	}
	
	return 0;
}