Cod sursa(job #1371605)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 3 martie 2015 22:49:45
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 300 + 2;
const double EPS = 1e-12;

long double A[Nmax][Nmax];
long double SOL[Nmax];

int N, M;

const int DIM_BUFF = ( 1 << 20 );

char buffer[DIM_BUFF];
int position = DIM_BUFF;

char GetChar()
{
    if ( position == DIM_BUFF )
    {
        fread( buffer, 1, DIM_BUFF, stdin );
        position = 0;
    }

    return buffer[ position++ ];
}

int rd()
{
    int nr = 0;
    int sgn = 1;
    char c;

    do
    {
        c = GetChar();

        if ( c == '-' )
        {
            sgn = -1;
        }

    } while ( !isdigit( c ) );

    do
    {
        nr = nr * 10 + ( c - '0' );
        c = GetChar();

    } while ( isdigit( c ) );

    return nr * sgn;
}

void read()
{
    freopen("gauss.in", "r", stdin);

    N = rd(); M = rd();

    for ( int i = 1; i <= N; ++i )
    {
        for ( int j = 1; j <= M + 1; ++j )
                A[i][j] = rd();
    }
}

void gauss()
{
    int i = 1, j = 1;

    while ( i <= N && j <= M )
    {
        int x = 0;

        for ( int k = i; k <= N; ++k )
        {
            if ( A[k][j] > EPS || A[k][j] < -EPS )
            {
                x = k;
                break;
            }
        }

        if ( !x )
        {
            j++;
            continue;
        }

        swap(A[i], A[x]);

        for ( int k = j + 1; k <= M + 1; ++k )
            A[i][k] /= A[i][j];

        A[i][j] = 1;

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

            A[l][j] = 0;
        }

        i++; j++;
    }
}

void solve()
{
    ofstream out("gauss.out");

    for ( int i = N; i >= 1; i-- )
    {
        for ( int j = 1; j <= M + 1; ++j )
        {
            if ( A[i][j] > EPS || A[i][j] < -EPS )
            {
                if ( j == M + 1 )
                {
                    out << "Imposibil\n";
                    return;
                }

                SOL[j] = A[i][M + 1];

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

                break;
            }
        }
    }

    for ( int i = 1; i <= M; ++i )
        out << fixed << setprecision( 12 ) << SOL[i] << " ";
}

int main()
{
    read();
    gauss();
    solve();

    return 0;
}