Cod sursa(job #1808750)

Utilizator afkidStancioiu Nicu Razvan afkid Data 18 noiembrie 2016 01:16:31
Problema Algoritmul lui Gauss Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include <bits/stdc++.h>
using namespace std;
// Gauss-Jordan elimination.
// Returns: number of solution (0, 1 or INF)
#define INF 0x3f3f3f3f
#define EPS 1e-15

int gauss (vector < vector<double> > a, vector<double> & ans) {
    int n = (int) a.size();
    int m = (int) a[0].size() - 1;
 
    vector<int> where (m, -1);
    for (int col=0, row=0; col<m && row<n; ++col) {
        int sel = row;
        for (int i=row; i<n; ++i)
            if (abs (a[i][col]) > abs (a[sel][col]))
                sel = i;
        if (abs (a[sel][col]) < EPS)
            continue;
        for (int i=col; i<=m; ++i)
            swap (a[sel][i], a[row][i]);
        where[col] = row;
 
        for (int i=0; i<n; ++i)
            if (i != row) {
                double c = a[i][col] / a[row][col];
                for (int j=col; j<=m; ++j)
                    a[i][j] -= a[row][j] * c;
            }
        ++row;
    }
 
    ans.assign (m, 0);
    for (int i=0; i<m; ++i)
        if (where[i] != -1)
            ans[i] = a[where[i]][m] / a[where[i]][i];
    for (int i=0; i<n; ++i) {
        double sum = 0;
        for (int j=0; j<m; ++j)
            sum += ans[j] * a[i][j];
        if (abs (sum - a[i][m]) > EPS)
            return 0;
    }

    // If we need any solution (in case INF solutions), we should be
    // ok at this point.
    // If need to solve partially (get which values are fixed/INF value):
//    for (int i=0; i<m; ++i)
//        if (where[i] != -1) {
//            REP(j,n) if (j != i && fabs(a[where[i]][j]) > EPS) {
//                where[i] = -1;
//                break;
//            }
//        }
    // Then the variables which has where[i] == -1 --> INF values
 
    for (int i=0; i<m; ++i)
        if (where[i] == -1)
            return INF;
    return 1;
}

int n,m;
double P;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("gauss.in","r",stdin);
    freopen("gauss.out","w",stdout);
    cin>>n>>m;
    vector<vector<double> > A(n);
    vector<double> ANS(n);
    for(int i=0;i<n;++i) {
        for(int j=0;j<m+1;j++) {
            cin>>P;
            A[i].push_back(P);
        }
    }
    int res = gauss(A,ANS);
    if(res==0) {
        cout<<"Imposibil\n";
    } else {
        for(int j=0;j<ANS.size();++j)
            cout<<fixed<<setprecision(8)<<ANS[j]<<" ";
        cout<<"\n";
    }
    return 0;
}