Problema B - Faraó
O poderoso faraó Ramsoni decidiu mandar construir duas pirâmides, uma
para lhe servir de túmulo a ele e outra para a sua esposa, a rainha
Nefertitioi. Ele quer que as pirâmides sejam enormes, mas há uma
pequena dificuldade: o Egipto está tão cheio de pirâmides, que já há
pouco espaço para construir mais.
O Problema
Escreva um programa que dado um mapa rectangular no Egipto onde estão
assinaladas todas as pirâmides existentes, calcule o máximo volume
combinado das duas pirâmides que se podem construir nos espaços ainda
livres. Dito de outro modo, de todos os pares de novas pirâmides
possíveis, queremos escolher aquelas cuja soma dos volumes seja o
maior possível. Todas as pirâmides (as já construídas e estas novas)
têm base quadrada e a altura é igual ao lado da base. Recorde que o
volume da pirâmide é um terço da área da base vezes a altura.
Input
Na primeira linha vêm dois números, B e
H, representado o medida da base e a medida da altura do
rectângulo que contém o mapa do Egipto, em decâmetros (1 ≤ B, H
≤ 300). Na segunda linha, vem um número N, o número de
pirâmides já construídas (0 ≤ N ≤ 100). Nas N
linhas seguintes vêm três números, X, Y e L,
descrevendo cada uma das pirâmides: X é a coordenada horizontal
do canto inferior esquerdo da base da pirâmide, Y é a
coordenada vertical desse ponto e L é o comprimento do lado da
base da pirâmide (que é igual à altura). Uma unidade representa um
decâmetro. Em todos os casos, temos 0 ≤ X ≤ B - L, 0
≤ Y ≤ H - L e 1 ≤ L ≤ 300. Todos os
rectângulos são disjuntos, dois a dois, mas podem tocar-se nos lados
ou nos cantos.
Output
Uma única linha, na qual existe um único número: o volume, em
decâmetros cúbicos, das duas pirâmides que em conjunto são mais
volumosas e que se podem construir no espaço livre no Egipto (nota que
as pirâmides são disjuntas, mas podem tocar noutras pirâmides nos
lados ou nos cantos). Em todos os casos de teste, é sempre possível
construir duas pirâmides. Pode existir mais do que um par que dê o
volume máximo. O número deve ser escrito arredondado a duas casas
decimais.
Exemplo de Input
15 10
5
0 1 4
5 6 4
1 7 1
10 1 1
10 4 3
Exemplo de Output
93.33
Selecção dos Concorrentes Portugueses
Olimpíadas Internacionais de Informática 2008
(1 de Agosto de 2008)