Problema do volume livre no box (ACM 2002)

From AdonaiMedrado.Pro.Br
Revision as of 12:25, 10 November 2008 by Adonaimedrado (Talk | contribs)

Jump to: navigation, search
Tradução do Problema A (Ballons 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 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.

Saída

Para cada 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.

Exemplo de entrada

2
0 0 0
10 10 10
3 3 3
7 7 7
0

Exemplo de saida

Box 1: 774