#include <iostream>
#include <stdlib.h>
using namespace std;
typedef float matrice[101][101];
int scrivinum();
void scrivimatr(matrice, int, char);
void stampamatr(matrice, int);
void scalini(matrice, int);
int indpivot(matrice, int, int);
float valpivot(matrice, int, int);
void scambiarighe(matrice, int, int, int);
bool sistemacolonne(matrice, int, int, int);
void sottraimultiploriga(matrice, int, int, int, float);
void annullacoeff(matrice, int);
void ridotta(matrice, int);
void pulisci(matrice, int);

int main() {
    matrice x;
    int n = scrivinum();
    scrivimatr(x, n, 'x');
    cout << endl << endl << endl;
    stampamatr(x, n);
    scalini(x, n);
    ridotta(x, n);
    cout << endl;
    stampamatr(x, n);
    system("PAUSE");
    return 0;
}


int scrivinum() {
    int a;
    do {
        cout << "Inserisci un numero compreso tra 1 e 100: ";
        cin >> a;
        cout << endl;
    } while ((a > 100) || (a < 0));
    return a;
}

void scrivimatr(matrice matr, int n, char s) {
    for (int i = 1; i <= n; i++) {
        cout << "inserisci la riga " << i << " di " << s << ":";
        for (int j = 1; j <= n; j++) {
            cout << endl;
            cin >> matr[i][j];
        }
        cout << endl;
    }
    cout << endl;
    return;
}

void stampamatr(matrice matr, int n) {
    cout << endl << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << matr[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl << endl;
    return;
}


bool sistemacolonne(matrice matr, int n, int colonna, int innesco) {
    bool m = true;
    int i = innesco;
    while ((i <= n) && m) {
        if (matr[i][colonna] != 0) {
            scambiarighe(matr, n, innesco, i);
            if (i != innesco) {
                cout << "\n\n" << "Scambiate le righe " << innesco << " e " << i << endl;
                stampamatr(matr, n);
            }
            m = false;
        }
        i++;
    }
    return !m;
}

void scalini(matrice matr, int n) {
    float fatt;
    int pivot = 1;
    for (int i = 1; i <= n; i++) {//per ogni colonna
        bool mark = sistemacolonne(matr, n, i, pivot);//mette un non-0 come primo elemento della riga i, se può, partendo da tante righe quanti pivot ha trovato
        cout << endl;
        if (mark) {  // se c'è un elemento non nullo nella colonna
            for (int j = pivot + 1; j <= n; j++) {//per ogni riga sotto quella di pivot
                fatt = matr[j][i] / matr[pivot][i];
                sottraimultiploriga(matr, n, j, pivot, fatt); //sottrae la riga di pivot moltiplicata per il giusto fattore
            }
            pivot++; //se si è trovato un pivot, segnalalo
        }
    }
    return;
}

int indpivot(matrice matr, int n, int riga) {
    int o = 0;
    int i = 1;
    while ((i <= n) && (o == 0)) {
        if (matr[riga][i] != 0) o = i;
        i++;
    }
    return o;
}

float valpivot(matrice matr, int n, int riga) {
    int i = 1;
    float pivot = 0;
    while ((i <= n) && (pivot == 0)) {
        if (matr[riga][i] != 0) pivot = matr[riga][i];
        i++;
    }
    return pivot;
}


void scambiarighe(matrice matr, int n, int riga1, int riga2) {
    float appo;
    for (int i = 1; i <= n; i++) {
        appo = matr[riga1][i];
        matr[riga1][i] = matr[riga2][i];
        matr[riga2][i] = appo;
    }
    return;
}

void sottraimultiploriga(matrice matr, int n, int sottratta, int toglie, float fatt) {
    for (int i = 1; i <= n; i++) matr[sottratta][i] = matr[sottratta][i] - (matr[toglie][i] * fatt);
    if ((fatt != 0) && (sottratta != toglie)) {
        cout << "Sottratta alla riga " << sottratta << " la riga " << toglie << " moltiplicata per " << fatt;
        stampamatr(matr, n);
    }
    return;
}

void annullacoeff(matrice matr, int n) {
    float fatt;
    for (int i = 1; i <= n; i++) {
        if ((valpivot(matr, n, i)) != 0) {
            fatt = valpivot(matr, n, i);
            for (int j = 1; j <= n; j++) matr[i][j] = matr[i][j] / fatt;
            if (fatt != 1) {
                cout << "Moltiplicata la riga " << i << " per " << fatt;
                stampamatr(matr, n);
            }
        }
    }
    return;
}

void ridotta(matrice matr, int n) {
    annullacoeff(matr, n);
    float fatt;
    int ind;
    for (int i = n; i > 1; i--) {
        if (indpivot(matr, n, i) != 0) {
            ind = indpivot(matr, n, i);
            for (int j = i - 1; j >= 1; j--) {
                fatt = matr[j][ind];
                sottraimultiploriga(matr, n, j, i, fatt);
            }
        }
    }
    pulisci(matr, n);
    return;
}

void pulisci(matrice matr, int n) {
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (fabs(matr[i][j]) < 0.00000001) matr[i][j] = 0;
    return;
}