Volume of an irregular tetrahedron

Find the volume of an irregular tetrahedron form its edges:

Suppose you are given the 6 sides of an irregular tetrahedron and you need to find the volume consumed by it.

Let the given sides to be u, v, w, W, V, U. Here, (u, U), (v, V), (w, W) are considered to be opposite edge pairs ( opposite edges means the edges which do not share common vertices ). Now the volume can be found from the following formula:

Let:
u′ = v² + w² - U²
v′ = w² + u² - V²
w′ = u² + v² - W²
Now:
volume = ¹⁄₁₂ × √(4u²v²w² - u²u′² - v²v′² - w²w′² + u′v′w′)

This formula is derived from the determinant which can be found here for more reading. As the formula is symmetric, the ordering of the pairs won't make any change to the formula.

Read more properties about Tetrahedrons from Wikipedia.

Contest Template

C++ contest coding template. Edit:5.

/*
USER: zobayer
TASK: template
ALGO: template
*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ALL(c) c.begin(), c.end()
#define SIZE(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 __int64
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const double BIG = 1e19;
const int INF = 0x7f7f7f7f;

int main() {
    //READ("in.txt");
    //WRITE("out.txt");
    return 0;
}

Segment-Circle Intersection

This is a sample code which verifies whether a given Circle and Segment intersects or not.

/*
**  Verifies the intersection of a segment and a circle
**  The line segment is defined from points p1 to p2
**  The circle is of radius r and centered at point c
**  There are potentially two points of intersection given by
**  p = p1 + mu1 (p2 - p1)
**  p = p1 + mu2 (p2 - p1)
**  mu1 and mu2 are updated via reference
**  Return FALSE if the segment doesn't intersect the circle
*/
bool cross(POINT p1, POINT p2, CIRCLE p, double &mu1, double &mu2) {
    double a, b, c, d;
    POINT t;
    t.x = p2.x - p1.x;
    t.y = p2.y - p1.y;
    a = sq(t.x) + sq(t.y);
    b = 2.0 * (t.x * (p1.x - p.c.x) + t.y * (p1.y - p.c.y));
    c = sq(p.c.x) + sq(p.c.y);
    c += sq(p1.x) + sq(p1.y);
    c -= 2.0 * (p.c.x * p1.x + p.c.y * p1.y);
    c -= sq(p.r);
    d = b * b - 4 * a * c;
    if(fabs(a) < eps || d < -eps) {
        mu1 = mu2 = 0.0;
        return false;
    }
    mu1 = (-b + sqrt(d)) / (2.0 * a);
    mu2 = (-b - sqrt(d)) / (2.0 * a);
    return true;
}

SPOJ Hints

Thanks to the Japanese boy, from whom I got this list. But unfortunately I could not read his name.. (Sorry! I can't read Japanese language.)

I've edited the list and added some myself (uploaded on Google Docs). This list is going to updated time by time...

Here is the file, have a look.
[Last updated: Thursday, November 12, 2009]

If any mistake is found, please comment out here. Thanks...