Cod sursa(job #801217)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 23 octombrie 2012 19:00:56
Problema Algoritmul lui Gauss Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 305;
const double Eps = 1e-11;

vector<double> A[MaxN];
int N, M;
double X[MaxN];
bool Sol;

void ComputeSolution() {
    Sol = true;
    for (int i = 1, j; i <= N; ++i) {
        for (j = 1; j <= M+1; ++j)
            if (abs(A[i][j]) > Eps)
                break;
        if (j == M+1) {
            Sol = false; return;
        }
        X[j] = A[i][M+1]/A[i][j];
    }
}

inline void Reduce(vector<double> &L1, vector<double> &L2, double C) {
    for (int i = 1; i <= M+1; ++i)
        L1[i] += C*L2[i];
}

void Gauss() {
    int i = 1, j = 1;
    while (i <= N && j <= M) {
        int k;
        for (k = i; k <= N && abs(A[k][j]) < Eps; ++k);
        if (k == N+1) {
            ++j; continue;
        }
        swap(A[i], A[k]);
        for (int k = 1; k <= N; ++k)
            if (i != k)
                Reduce(A[k], A[i], -A[k][j]/A[i][j]);
        ++i, ++j;
    }
}

void Read() {
    assert(freopen("gauss.in", "r", stdin));
    assert(scanf("%d %d", &N, &M) == 2);
    for (int i = 1; i <= N; ++i) {
        A[i].resize(M+2);
        for (int j = 1; j <= M+1; ++j)
            assert(scanf("%lf", &A[i][j]) == 1);
    }
}

void Print() {
    assert(freopen("gauss.out", "w", stdout));
    if (!Sol) {
        printf("Imposibil\n"); return;
    }
    for (int i = 1; i <= M; ++i)
        printf("%.11lf ", X[i]);
    printf("\n");
}

int main() {
    Read();
    Gauss();
    ComputeSolution();
    Print();
    return 0;
}