Solução Praça do Retângulo

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

 

Para cada ponto P iremos olhar todos os pontos anteriores a ele que podem formar um retângulo com ele. Para tal, vamos usar duas pilhas, a pilha cima, que guarda os pontos com y maior que a coordenada y de P, e a pilha baixo para os pontos com coordenada y menor.

Olhando agora cada ponto Q anterior ao ponto P, ordenadamente segundo a coordenada x, suponha que o y de Q seja maior que o de P. O ponto do topo da pilha cima não pode ter y menor que Q, pois se isso ocorrer, Q estaria dentro do retângulo que ele formaria com P. Por isso, devemos excluir o topo da pilha enquanto sua coordenada Y for maior que a de Q. Note que, assim, a pilha se mantêm sempre crescente e por isso só preciso excluir os elementos de seu topo para garantir que, em toda ela, não há elementos anteriores a Q com valor de y maior. De maneira análoga, se Q tiver y menor que P, devemos excluir o topo da pilha baixo enquanto seu valor de y for menor que o de Q.

Para cada ponto P, os elementos em cima e em baixo são pontos que podem formar retângulos com P e P é o ponto mais à direita, logo se repetirmos o algoritmo para cada ponto P, adicionando à resposta a soma dos tamanhos de cima e baixo, não contaremos nenhum retângulo duas vezes.

Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: