Cod sursa(job #608675)

Utilizator crushackPopescu Silviu crushack Data 17 august 2011 17:01:35
Problema Algoritmul lui Gauss Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#include <algorithm>
#define NMax 310
using namespace std;

const char IN[]="gauss.in",OUT[]="gauss.out";

int N,M;
int P[NMax];
double A[NMax][NMax] , R[NMax];

inline double abs(double const &x){
    return x<0 ? -x : x;
}

inline void swaprow(int x,int y){
    int i;
    for (i=0;i<=M;++i) swap(A[x][i],A[y][i]);
}

void solve()
{
    int i,j,k,l,maxi;
    double p;

    for (i=0;i<N;++i) P[i]=-1;
    for (i=j=0;i<N && j<M;++j)
    {
        /*for (k=i+1;k<N && ;++k)
            maxi= abs(A[k][j])>abs(A[maxi][j]) ? k : maxi;*/
        for (k=i;k<N && !A[k][j];++k);
        maxi=k;
        if (A[maxi][j])
        {
            for (k=0;k<=M;++k) swap(A[maxi][k],A[i][k]);
            p=A[i][j];
            for (k=0;k<=M;++k) A[i][k]/=p;
            for (k=i+1;k<N;++k)
            {
                p=A[k][j];
                for (l=j;l<=M;++l)
                    A[k][l]-= A[i][l]*p;
            }
            P[i]=j;
            ++i;
        }
    }
}

int main()
{
    int i,j,k,x;

    freopen(IN,"r",stdin);
    scanf("%d%d",&N,&M);
    for (i=0;i<N;++i)
        for (j=0;j<=M;++j) scanf("%d",&x),A[i][j]=x;
    fclose(stdin);

    if ( M==1 )
    {
        freopen(OUT,"w",stdout);
        if (A[0][0]) printf("%lf\n",A[0][1]/A[0][0]);
        else if (!A[0][1]) printf("%.8lf\n",0.);
        else printf("Imposibil\n");
        return 0;
    }

    solve();

    for (i=N-1,j=M-1;i>=0;--i)
    {
        if (P[i]==-1) continue;
        //while (!A[i][j]) --j;
        while (j>P[i]) R[j]=0,--j;
        R[j]=A[i][M];
        for (k=M-1;k>P[i];--k)
            R[j]-=A[i][k]*R[k];
        --j;
    }
    while (j>=0) R[j]=0,--j;

    for (i=0;i<N;++i)
    {
        for (j=0;j<M && A[i][j]==0;++j);
        if (j==M && A[i][M]!=0) break;
    }

    freopen(OUT,"w",stdout);
    if (i<N) printf("Imposibil"); else
    for (i=0;i<M;++i) printf("%.8lf ",R[i]);
    printf("\n");
    fclose(stdout);
    return 0;
}