SPOJ Brasil

O diagrama de Voronoi é muito famoso na matemática e computação. Nomeado em homenagem a Georgi Voronoi, seu objetivo é, dado um conjunto S de pontos no plano, determinar, para cada ponto p, a região V(p) onde todos os pontos dali estão mais próximos de p do que de qualquer outro ponto de S.

É muito fácil encontrar aplicações para o diagrama. Suponha, por exemplo, que você tenha o mapa de uma cidade, e a localização de todos os cyber-cafés. Assim, toda vez que você estiver em algum lugar da cidade, e precisar verificar se algum amigo mandou um e-mail novo, pode facilmente achar o mais próximo. Outra possibilidade seria se em vez de cyber-cafés tivéssemos hospitais ou postos de saúdes, mas claramente o primeiro exemplo é mais importante.

É possível estender o conceito do diagrama para mais dimensões. Estamos, aqui, interessados no caso tri-dimensional. Como a implementação é trivial, os juízes fizeram as deles, enquanto jogavam uma partidinha de War (que o exército azul ganhou). Para o término do programa faltou apenas uma função que eles não entraram em acordo. É sobre calcular o volume de um sólido formado por quatro pontos A, B, C e D. Um dos juízes, disse que a fórmula é Área da Base × Altura/3. O outro falou que é Altura × Área da Base/3. Sua tarefa é fazer um programa que leia os pontos A, B, C e D e imprima o volume do sólido formado por eles.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância terá quatro linhas. Cada linha conterá as coordenadas X, Y e Z dos pontos A, B, C e D, respectivamente. As coordenadas são separadas por um espaço.

Restrições

0 <= X, Y, Z <= 1000
A != B != C != D

Saída

Para cada instância, imprima, com precisão de até 6 casas decimais, o volume do sólido.

Exemplo de entrada

1
0 0 0
10 10 0
20 0 0
10 5 10

Saída para o exemplo de entrada

333.333333

Comentários

Aviso: Na maratona você não tem acesso à internet. Logo, não estrague a brincadeira procurando a fórmula na internet.