Difference between revisions of "Problema do volume livre no box (ACM 2002)"
(New page: 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 program...) |
|||
| Line 1: | Line 1: | ||
| − | Tradução do Problema A (Ballons in a Box) | + | Tradução do Problema A (Ballons in a Box) em |
| + | The 2002 26th Annual acm International Collegiate: Programming Contest World Finals | ||
== Dificuldade Única == | == Dificuldade Única == | ||
| Line 12: | Line 13: | ||
A entrada termina com o número zero um uma linha. | 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 | ||
Revision as of 12:25, 10 November 2008
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
