Problema do volume livre no box (ACM 2002)
Tradução do Problema A (Balloóns in a Box) em
The 2002 26th Annual acm International Collegiate: Programming Contest World Finals
Dificuldade Única
Você deve escrever um programa para simular a colocação de balões esféricos em um box retangular.
O cenário de simulação é o seguinte. Imagine que lhe será fornecido um box retangular e um conjunto de pontos. Cada ponto representa a posição 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 box ou do balã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 objetivo é dispor os balões no box de forma a maximizar 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.
Nome do arquivo de entrada: balloon.in.
Saída
Para cada caso de teste imprima uma linha na saída com o número do caso de teste seguindo pelo volume do box não ocupado por balões. Arredonde o volume para o inteiro mais próximo. Siga o formato do exemplo de saída abaixo.
Coloque um linha em branco depois da saída de cada caso de teste.
Nome do arquivo de saída: balloon.out.
Exemplo de entrada
2 0 0 0 10 10 10 3 3 3 7 7 7 0
Exemplo de saida
Box 1: 774
