Cod sursa(job #1518628)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 6 noiembrie 2015 00:37:13
Problema Algoritmul lui Gauss Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.68 kb
#include <bits/stdc++.h>

using namespace std;

class Scanner
{
private:

    FILE *inputFile;
    int cursor;

    static const int MAX_SIZE = 1 << 16;
    char buffer[MAX_SIZE];

    inline char getChar()
    {
        if (cursor == MAX_SIZE)
        {
            cursor = 0;
            fread(buffer, MAX_SIZE, 1, inputFile);
        }

        return buffer[cursor++];
    }

    inline int getNr()
    {
        int a = 0;
        int sign = 1;
        char ch;

        do
        {
            ch = getChar();

        } while (!isdigit(ch) && ch != '-');

        if (ch == '-')
        {
            sign = -1;
            ch = getChar();
        }

        do
        {
            a = (a << 3) + (a << 1) + (ch - '0');
            ch = getChar();

        } while (isdigit(ch));

        return a * sign;
    }

public:

    Scanner() {
    }

    Scanner(const char *file)
    {
        inputFile = fopen(file, "r");
        cursor = MAX_SIZE;
    }

    inline Scanner& operator >> (int &x)
    {
        x = getNr();
        return *this;
    }
};


const double EPS = 1e-10;

const int MAX_N = 300 + 2;

double A[MAX_N][MAX_N];
double solution[MAX_N];

int N, M;

int main()
{
    Scanner in("gauss.in");
    ofstream out("gauss.out");

    in >> N >> M;

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M + 1; ++j)
        {
            int x;
            in >> x;

            A[i][j] = x;
        }

    int i = 1, j = 1;

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

        while (p <= N)
        {
            if (fabs(A[p][j]) > EPS)
            {
                k = p;
                break;
            }
        }

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

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

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

        A[i][j] = 1.0;

        for (int l = i + 1; l <= N; ++l)
        {
            double coef = A[l][j];

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

        i++; j++;
    }

    for (int i = N; i >= 1; i--)
    {
        int j = 1;

        while (j <= M + 1)
        {
            if (fabs(A[i][j]) > EPS)
            {
                if (j == M + 1)
                {
                    out << "Imposibil\n";
                    return 0;
                }

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

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

                break;
            }

            j++;
        }
    }

    for (int i = 1; i <= M; ++i)
        out << fixed << setprecision(8) << solution[i] << " ";

    out << endl;

    return 0;
}