Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DVORONOI - Diagrama de Voronoi

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.


Adicionado por:Wanderley Guimarăes
Data:2009-08-31
Tempo limite:0.166s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO OBJC PERL6 PY_NBC SCALA TCL
Origem:Segunda Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2010-03-29 16:49:08 Rodrigo Maia
Nas restriçőes falam em: "1 <= X, Y, Z <= 1000", só que no exemplo de entrada colocam, na segunda linha: "0 0 0
".
Năo entendi, poderiam me explicar.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.