Cod sursa(job #1267887)

Utilizator teoionescuIonescu Teodor teoionescu Data 20 noiembrie 2014 14:02:09
Problema Algoritmul lui Gauss Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include<fstream>
#define abs(x) ((x>0)?(x):(-(x)))
using namespace std;
ifstream in("gauss.in");
ofstream out("gauss.out");
typedef double ld;
const int Nmax = 302;
const ld eps = 1e-6;
int N,M;
int a[Nmax][Nmax];
ld A[Nmax][Nmax];
ld Ans[Nmax];
int Nul[Nmax];
void divide(int ind,ld coef){
    for(int j=1;j<=M+1;j++) A[ind][j]/=coef;
}
void swap(int i,int j){
    for(int k=1;k<=M+1;k++) swap(A[i][k],A[j][k]);
}
void substract(int i,int j){
    for(int k=1;k<=M+1;k++) A[i][k]-=A[j][k];
}
int main(){
    in>>N>>M;
    for(int i=1;i<=N;i++) for(int j=1;j<=M+1;j++) in>>a[i][j];
    for(int i=1;i<=N;i++) for(int j=1;j<=M+1;j++) A[i][j]=ld(a[i][j]);
    int row=1,col=0;
    while(row<=N && col<=M){
        col++;
        int pos=0;
        while(col<=M && !pos){
            for(int i=row;i<=N;i++) if(!pos && A[i][col]!=0) pos=i;
            if(!pos) Nul[col++]=1;
        }
        swap(row,pos);
        for(int i=row;i<=N;i++) if(A[i][col]!=0) divide(i,A[i][col]);
        for(int i=row+1;i<=N;i++) if(A[i][col]!=0) substract(i,row);
        row++;
    }
    row=N;
    for(int col=M;col>=1;col--){
        while(A[row][col]==0.) row--;
        while(A[row][col]!=1.) col--;
        if(!Nul[col]){
            Ans[col]=A[row][M+1];
            for(int j=col+1;j<=M;j++) Ans[col]-=Ans[j]*A[row][j];
        }
    }
    for(int i=1;i<=N;i++){
        ld X=0;
        for(int j=1;j<=M;j++) X+=Ans[j]*ld(a[i][j]) ;
        if( abs( X - ld(a[i][M+1]) ) > eps ){
            out<<"Imposibil\n";
            return 0;
        }
    }
    out.precision(8);
    for(int i=1;i<=M;i++){
        if(Nul[i]) out<<0<<' ';
        else out<<fixed<<Ans[i]<<' ';
    }
    out<<'\n';
    return 0;
}