Solução Praça do Retângulo

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:

https://gist.github.com/rogerioagjr/78a78634bb4c4a27fe907e03741c93dc