Problema B - Arranha-Céus


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

Problema:
Dadas as coordenadas inteiras 2D de uma sequência de rectângulos, estando a sequência ordenada pela distância crescente em relação ao ponto de onde tiras a foto (coordenada Z), a tarefa é calcular duas coisas: o número de rectângulos visíveis e o maior overlap de rectângulos da sequência.

Restrições:
1 ≤ N ≤ 3 000
1 ≤ X1i, X2i, Yi ≤ 2 000 000 000


Solução base:
Se as coordenadas dos rectângulos forem reduzidas (e.g. < 1000), é possível guardar uma matriz em memória que represente uma grelha onde se "pintam" os rectângulos consoante as suas coordenadas.

Esta abordagem teria uma complexidade temporal de O(N*X*Y), mas teria problemas ao nível do consumo excessivo de memória. Assim, obteria cerca de 35 pontos.


Compressão de coordenadas
Na verdade, as coordenadas dos pontos não são relevantes por si só, apenas é útil saber se um rectângulo está mais à esquerda, à direita ou no mesmo xx de outro rectângulo, ou se tem altura maior, igual ou menor.
Deste modo, podemos ordenar os yy e os xx dos rectângulos e, em vez de usar as coordenadas, usamos apenas o seu número de ordem. Exemplo: em vez da coordenada yy estar compreendida no intervalo [1, 2 000 000 000], passa-se a usar o número de ordem - 1,2,3,..N yy mais pequeno.

Esta abordagem já não depende das coordenadas dos rectângulos mas apenas do número de rectângulos.
A complexidade temporal seria O(N^3) e obteria cerca de 70 pontos.


Sweep Line + divisão em intervalos
Em primeiro lugar, se um rectângulo for visível, será sempre visível (pelo menos) no seu Y máximo, visto que todos os rectângulos começam todos em Y = 1.

Por outro lado, vendo os rectângulos da esquerda para a direita, podemos definir um conjunto de 2*N eventos: o X1 e X2 (início e fim) de cada rectângulo.

Assim, ordenando estes eventos por ordem crescente, podemos registar para cada intervalo de xx o número de rectângulos que contêm todo ou uma parte desse intervalo e qual é o índice do rectângulo presente neste intervalo que está mais próximo (coordenada Z, ou seja, ordem de ocorrência no input).

Posto isto, percorrem-se os rectângulos por ordem decrescente de Y (Sweep Line)e para cada um deles devem-se actualizar os 2*N intervalos de eventos. Para saber se um rectângulo é visível, basta que ao processá-lo exista algum intervalo cujo rectângulo mais próximo esteja, de facto, mais longe que o triângulo que está em processamento.

Para cada um dos N rectângulos, percorrem-se no máximo 2*N intervalos. Assim, esta abordagem teria uma complexidade temporal de O(N^2), sendo merecedora dos 100 pontos.


Ligações interessantes: