Cod sursa(job #770984)

Utilizator mi5humihai draghici mi5hu Data 24 iulie 2012 15:01:22
Problema Algoritmul lui Gauss Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.49 kb
#include <stdio.h>
#include <cmath>
#define NMAX 302
#define eps 0.0000000001

using namespace std;

double a[NMAX][NMAX+1];
int Pivot[NMAX];
int Line[NMAX];
double Rez[NMAX];

int n, m;

void read_() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m + 1; j++) {
            scanf("%lf", &a[i][j]);
        }
    } 
}

bool get_sol() {
    for (int j = m; j>= 1; j--) {
        int i = Line[j];
        if (i != 0) {
            Rez[j] = a[i][m + 1] / a[i][j];
            for (int ii = 1; ii <= n; ii++) {
                a[ii][m + 1] -= (a[ii][j] * Rez[j]);
            }
        } else {
            
            if (fabs(a[i][j]) > eps && j <= n) {
                return false;           
            }
            Rez[j] = 0;       
        }                
    }
    return true; 
}

bool check_() {
    if (n > m) {
        for (int i = 1; i <= n; i++) {
           if (Pivot[i] == 0 && fabs(a[i][m + 1]) > 2 * eps) {
               return false;
           }
        }
        return true; 
    } 
    return true;
}

bool solve_() {
    int Ln, i, j, ii, jj;
    int diagN = n < m ? n : m;
    
    for (j = 1; j <= diagN; j++) {
        double maxx = eps;
        Ln = 0;
        for (i = 1; i <= n; i++) {
             if (Pivot[i] == 0 && (fabs(a[i][j]) > maxx)) {
                 maxx = fabs(a[i][j]);
                 Ln = i;
             } 
        }
        
        if (Ln == 0) {
             continue;         
        }
        i = Ln;        
        double  val = a[i][j];
        for (jj = j; jj <= m + 1; jj++) {                    
            a[i][jj] /= val;
        }                          
        Pivot[i] = j;                 
        Line[j] = i;        
        for (ii = 1; ii <= n; ii++) {
            if (Pivot[ii] == 0 && (a[ii][j] > eps || a[ii][j] < eps)) {
               val = a[ii][j];
               for (jj = j; jj <= m + 1; jj++) {
                   a[ii][jj] -= (a[i][jj] *val);
               }  
            }
        }
    }          
    return (get_sol() && check_());
}

void print_(bool sol) {
    if (sol == false) {
        printf("Imposibil");        
    } else {
        for (int i = 1; i <= m; i++) {
            printf("%.10lf ", Rez[i]);
        }
    }
}

int main() {
    freopen("gauss.in", "r", stdin);
    freopen("gauss.out", "w", stdout);
    
    read_();
    bool sol = solve_();
    print_(sol);
 
    return 0;
}