Cod sursa(job #1008564)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 11 octombrie 2013 12:17:39
Problema Algoritmul lui Gauss Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 kb
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <stack>
#include <iomanip>

#define pb push_back

#define mp make_pair
#define f first
#define s second
#define ll long long

const int MAXN = 305;
const double eps = 0.0000001;
using namespace std;


int N, M;
double X[MAXN], A[MAXN][MAXN];


inline void swap(double &a, double &b) {
    double aux = a;
    a = b;
    b = aux;
}

inline bool zero(double x) {
    return (x > -eps && x < eps);
}

void print_sol() {
    for (int i = N - 1; i >= 0; --i) {
        for (int j = 0; j <= M; ++j) {
            if (!zero(A[i][j])) {
                
                if (j == M) {
                    cout << "imposibil\n";
                    return ;
                }
                X[j] = A[i][M];
                for (int k = j + 1; k < M; ++k)
                    X[j] -= X[k] * A[i][k];
                break;
            }
        }
    }
    for (int i = 0; i < M; ++i)
        printf("%.10lf ",  X[i] ) ;
}
inline int get_nonzero(int t_l, int t_c) {
    
    for (int i = t_l + 1; i < N; ++i)
        if (!zero(A[i][t_c]))
            return i;
    return t_l;
}

inline void swap_lines(int l1, int l2) {
    for (int j = 0; j <= M; ++j)
        swap(A[l1][j], A[l2][j]);
}
int main() {
    freopen("gauss.in", "r", stdin);
    freopen("gauss.out", "w", stdout);

    cin >> N >> M;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j)
            cin >> A[i][j];
    }
    
    for (int i = 0, j = 0; i < N && j < M; ++i, ++j) {
        //i'th line, j'th column
        int t_k = get_nonzero(i, j);
        swap_lines(t_k, i);

        if (zero(A[i][j])) {
            ++j; 
            continue;
        } 
        
        for (int l = j + 1; l <= M; ++l)
            A[i][l] /= A[i][j];
        A[i][j] = 1.0;

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

    }
/*
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j) 
            cerr << A[i][j] << " " ;
        cerr << "\n";
    }
*/
    print_sol();
    return 0;
}