Problema do volume livre no box (ACM 2002)

Tradução do Problema A (Ballons in a Box) do The 2002 26th Annual acm International Collegiate: Programming Contest World Finals

Dificuldade Única

Você deve escrever um programa para simular a colocação de baloões esféricos em um box retangular.

O cenário de simulação é o seguinte. Imagine que lhe será fornecido um box retângular e um conjunto de pontos. Cada ponto representa a posiçãao onde você pode colocar um balão. Para colocar um balão neste ponto, deve-se centralizá-la no ponto e inflá-lo até que ele toque uma borda do retângulo ou um balação previamente colocado. Você não pode utilizar pontos fora do box ou dentro de outros balões já dispostos. Entretanto, você pode utilizar os ponto em qualquer ordem que desejar e não é necessário utilizar todos os pontos. Seu objtivo é dispor os balões no box de forma que maximize-se o volume total ocupado.

Pede-se um programa capaz de calcular o volume dentro do box que não está ocupado por balões.

Entrada

A entrada consiste de diversos casos de teste. A primeiro linha de cada caso de teste contém um único inteiro n que indica o número de pontos no conjunto (1<=n<=6). A segunda linha contém três inteiros que representam (x,y,z), coordenadas inteiras de um canto do box e a terceira linha contem (x,y,z) coordenadas inteiras do canto oposto do box. As próximas n linhas do restante do caso de uso contém três inteiros cada, representando (x,y,z) coordenadas do conjunto de pontos. O box tem tamanho não zero em cada dimensão e seus lados são paralelos aos eixos.

A entrada termina com o número zero um uma linha.