// gauss.cpp
// Liczy wyznacznik macierzy wymiernych metodą Gaussa.

#include <cassert>
#include <cmath>
#include <iostream>
#include <iomanip>

using namespace std;

class Rational {
    int p, q;   /* p/q,   q > 0 */
public:
	Rational(int p, int q = 1) {
		assert(q != 0);
		if (q < 0) {
			p = -p;
			q = -q;
		}
		int g = gcd(abs(p), q);
		
		this->p = p/g;
		this->q = q/g;
	}
	friend Rational operator+(const Rational &a, const Rational &b) {
		return Rational(a.p*b.q + b.p*a.q,  a.q*b.q);
	}
	friend Rational operator-(const Rational &a, const Rational &b) {
		return Rational(a.p*b.q - b.p*a.q,  a.q*b.q);
	}
	friend Rational operator*(const Rational &a, const Rational &b) {
		return Rational(a.p*b.p, a.q*b.q);
	}
	friend Rational operator/(const Rational &a, const Rational &b) {
		return Rational(a.p*b.q, a.q*b.p);
	}
	friend ostream & operator<<(ostream &out, const Rational &a) {
		out << a.p;
		if (a.q != 1) {
			out << "/" << a.q;
		}
		return out;
	}
	friend bool operator==(const Rational &a, const Rational &b) {
		return a.p == b.p && a.q == b.q;
	}
	friend bool operator!=(const Rational &a, const Rational &b) {
		return a.p != b.p || a.q != b.q;
	}
	
	Rational operator-() const { return Rational(-p, q); }
private:
	int gcd(int a, int b) const {
		int r;
		while (b != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
};

void printMatrix(Rational **A, int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << A[i][j] << "\t";
		}
		cout << "\n";
	}
	cout << endl;
}

inline void swap(Rational &a, Rational &b) {
	Rational c = a;
	a = b;
	b = c;
}

Rational determinant(Rational **A, int n) {
	cout << "Eliminacja Gaussa dla macierzy:\n";
	printMatrix(A,n);
	
	int sign = 1;	
	for (int k = 0; k < n; k++) {		
		if (A[k][k] == 0) {
			for (int s = k+1; s < n; s++) {
				if (A[s][k] != 0) {
					cout << "w" << s+1 << "  <=>  w" << k+1 << "\n";
					for (int j = k; j < n; j++) {
						swap(A[k][j], A[s][j]);
					}
					sign = -sign;
					break;
				}
			}
			if (A[k][k] == 0) {
				cout << "Macierz jest osobliwa." << endl;
				return 0;
			}
			printMatrix(A, n);
		}
		
		bool hasChanged = false;
		for (int i = k+1; i < n; i++) {
			if (A[i][k] != 0) {
				Rational m = A[i][k] / A[k][k];
				cout << "w" << i+1 << "  :=  w" << i+1
				     << " - (" << m << ")*w" << k+1 << "\n";
				for (int j = k; j < n; j++) {
					A[i][j] = A[i][j] - m * A[k][j];
				}
				hasChanged = true;
			}
		}
		if (hasChanged) {
			cout << endl;
			printMatrix(A, n);
		}
	}
	cout << "Eliminacja zakonczona sukcesem!" << endl;
	
	Rational det = 1;
	for (int k = 0; k < n; k++) {
		det = det * A[k][k];
	}
	
	return sign*det;
}


int main() {
	Rational A[4][4] = {
		{ 0, 0, 0, 4 },
		{ 0, 2, 0, 0 },
		{ 0, 0, 3, 0 },
		{ 1, 0, 0, 0 },
	};
	Rational *As[4] = { A[0], A[1], A[2], A[3] };
	
	cout << "detA = " << determinant(As, 4) << "\n\n" << endl;
	
	
	
	Rational B[7][7] = {
		{  2, -1,  0,  0,  0,  0,  0 },
		{ -1,  2, -1,  0,  0,  0,  0 },
		{  0, -1,  2, -1,  0,  0,  0 },
		{  0,  0, -1,  2, -1,  0,  0 },
		{  0,  0,  0, -1,  2, -1,  0 },
		{  0,  0,  0,  0, -1,  2, -1 },
		{  0,  0,  0,  0,  0, -1,  2 },
	};
	Rational *Bs[7] = { B[0], B[1], B[2], B[3], B[4], B[5], B[6] };
	
	cout << "detB = " << determinant(Bs, 7) << endl;


	Rational C[7][7] = {
		{  2, -1,  0,  0,  0,  0, -1 },
		{ -1,  2, -1,  0,  0,  0,  0 },
		{  0, -1,  2, -1,  0,  0,  0 },
		{  0,  0, -1,  2, -1,  0,  0 },
		{  0,  0,  0, -1,  2, -1,  0 },
		{  0,  0,  0,  0, -1,  2, -1 },
		{ -1,  0,  0,  0,  0, -1,  2 },
	};
	Rational *Cs[7] = { C[0], C[1], C[2], C[3], C[4], C[5], C[6] };
	
	cout << "detC = " << determinant(Cs, 7) << endl;
	
	
	
	Rational D[7][7] = {
		{ 1, 2, 3, 4, 5, 6, 7 },
		{ 2, 3, 4, 5, 6, 7, 6 },
		{ 3, 4, 5, 6, 7, 6, 5 },
		{ 4, 5, 6, 7, 6, 5, 4 },
		{ 5, 6, 7, 6, 5, 4, 3 },
		{ 6, 7, 6, 5, 4, 3, 2 },
		{ 7, 6, 5, 4, 3, 2, 1 },
	};
	Rational *Ds[7] = { D[0], D[1], D[2], D[3], D[4], D[5], D[6] };
	
	cout << "detD = " << determinant(Ds, 7) << endl;
	
	return 0;
}