Problema A - Pontos e Rectângulos

Tipo de problema: Geometria
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

Problema:
Dado um conjunto de pontos, quantos rectângulos que não possuem pontos no seu interior existem?

Restrições:
2 <= N <= 10 000.
1 <= Xi, Yi <= 2 000 000 000.

Solução base:
Colocar os pontos numa matriz.
Para cada par de pontos, verificar se existe algum ponto no seu interior.

Esta seria uma solução O(N^4) que daria aproximadamente 30 pontos.

Melhorar: para quê desenhar?
Obviamente que não precisamos de pesquisar todos os pontos no interior do rectângulo!
Podemos fazer o inverso, verificar se os pontos existentes estão dentro do rectângulo.

Esta seria uma solução O(N^3) que daria aproximadamente 40 pontos.

Melhorar a verificação
O próximo patamar estava reservado para aqueles programas que conseguem verificar instantaneamente se num dado rectângulo existe algum ponto.

Matriz original: 

 

 

 
  
1 
2 
3 
4 
5 
6 

 

 
1 
X  
. 
. 
. 
X  
. 

 

 
2 
. 
. 
. 
X  
. 
. 

 

 
3 
. 
. 
. 
. 
X  
. 

 

 
4 
. 
. 
. 
. 
. 
. 

 

 
5 
. 
. 
. 
. 
X  
. 

 

 
6 
X  
. 
. 
. 
. 
X

Matriz resultante: 

 

 

 
  
1 
2 
3 
4 
5 
6 

 

 
1 
1  
1 
1 
1 
2  
2 

 

 
2 
1 
1 
1 
2  
3 
3 

 

 
3 
1 
1 
1 
2 
4  
4 

 

 
4 
1 
1 
1 
2 
4 
4 

 

 
5 
1 
1 
1 
2 
5  
5 

 

 
6 
2  
2 
2 
3 
6 
7

A matriz de somas acumuladas permite-nos descobrir se existe algum ponto em qualquer sub-rectângulo em tempo constante! O(1)

Por exemplo, para calcular o número de pontos no rectângulo entre (3, 2) e (5, 5):

m[5][5] - m[2][5] - m[5][1] + m[2][1]

Esta seria uma solução O(N^2) em tempo, mas também O(N^2) em memória, pelo que daria 60 pontos.

Out of the box

Como manter a pesquisa em O(N^2) mas garantir que usamos menos de 32MB?
Ordenamos os pontos por uma coordenada (por exemplo Y), e para cada ponto verificamos: