SPOJ PIR

From Algorithmist
Jump to navigation Jump to search

use the formula for volume of irregular tetrahedral of given sides. first pair the given sides such that they don't have any common vertices. and name it (u,U),(v,V), (w,W) Volume = sqrt(4*u*u*v*v*w*w- u*u*sqr((v*v+w*w - U*U)) - v*v*sqr((w*w+u*u - V*V)) - w*w*sqr((u*u + v*v - W*W)) + (v*v +w*w - U*U)*(w*w+u*u- V*V)*(u*u+v*v - W*W))/12;

Also you can think in tartaglia theorem Determinant with: Leibniz and inversions with: fenwick tree.

Reference: http://www.cs.berkeley.edu/~wkahan/VtetLang.pdf