p162.in2
======================
1000 1000 1000 3 4 5


=================
p162.ans2
======================
1999.9937


=================
p162.in1
======================
1 1 1 1 1 1


=================
statement.txt
======================
162. Pyramids
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard input
output: standard output



Recently in Farland, a country in Asia, a famous scientist Mr. Log Archeo has discovered ancient pyramids. But unlike those in Egypt and Central America, they have triangular (not rectangular) foundation. That is, they are tetrahedrons in mathematical sense. In order to find out some important facts about the early society of the country (it is widely believed that the pyramid sizes are in tight connection with Farland ancient calendar), Mr. Archeo needs to know the volume of the pyramids. Unluckily, he has reliable data about their edge lengths only. Please, help him!

Input
The file contains six positive integer numbers not exceeding 1000 separated by spaces, each number is one of the edge lengths of the pyramid ABCD. The order of the edges is the following: AB, AC, AD, BC, BD, CD.

Output
A real number - the volume printed accurate to four digits after decimal point.

Sample test(s)

Input
Sample input #1
1 1 1 1 1 1

Sample input #2
1000 1000 1000 3 4 5

Output
Sample output #1
0.1179

Sample output #2
1999.9937

Note
Author:	Nikolay Durov
Resource:	ACM ICPC 2002-2003 NEERC, Northern Subregion
Date:	November, 2002







=================
p162.ans1
======================
0.1179


=================
p162.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

double AB, AC, AD, BC, BD, CD;

void read() { cin >> AB >> AC >> AD >> BC >> BD >> CD; }

double gaussian_det(vector<vector<double>> mat) {
    int n = mat.size();
    double det = 1.0;
    for(int i = 0; i < n; ++i) {
        int pivot = i;
        for(int j = i + 1; j < n; ++j) {
            if(abs(mat[j][i]) > abs(mat[pivot][i])) {
                pivot = j;
            }
        }
        if(pivot != i) {
            swap(mat[i], mat[pivot]);
            det = -det;
        }
        if(abs(mat[i][i]) < 1e-10) {
            return 0.0;
        }
        det *= mat[i][i];
        for(int j = i + 1; j < n; ++j) {
            double factor = mat[j][i] / mat[i][i];
            for(int k = i; k < n; ++k) {
                mat[j][k] -= factor * mat[i][k];
            }
        }
    }
    return det;
}

void solve() {
    // We know that the volume of the pyramid is 1/3 * h * B, where B is the
    // area of the base and h is the height. The area of the base can easily be
    // calculated with Heron's formula, while the height we can bash / compute
    // using complex numbers or by defining a vector base and solving a system.
    // This approach is a bit tedious so we might want to consider alternatives.
    //
    // There is also an alternative approach using more theory. We can use
    // Cayley-Menger's determinant, which can be thought of as a generalization
    // of Heron's formula. It essentially gives us a formula for the volume of
    // the n-dimensional simplex, given by the pairwise distances between all
    // points. In particular, the formula says that the determinant of the
    // pairwise distance matrix with 1s added as the final row and column, times
    // (-1)^(n+1)/((n!)^2*2^n) is the square of the volume of the n-dimensinoal
    // simplex. This is precisely what we have here for n=4 and so we implement
    // this. More details can be found here:
    //
    //     https://en.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant

    double a2 = AB * AB, b2 = AC * AC, c2 = AD * AD;
    double d2 = BC * BC, e2 = BD * BD, f2 = CD * CD;
    vector<vector<double>> m(5, vector<double>(5));
    m[0] = {0, 1, 1, 1, 1};
    m[1] = {1, 0, a2, b2, c2};
    m[2] = {1, a2, 0, d2, e2};
    m[3] = {1, b2, d2, 0, f2};
    m[4] = {1, c2, e2, f2, 0};
    double determinant = gaussian_det(m);
    double volume = sqrt(abs(determinant) / 288.0);
    cout << fixed << setprecision(4) << volume << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
