Problema B - Desenhando Quadrados

Tipo de problema: Matemática/Pesquisa
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

Problema:
Dado um conjunto de N pontos no plano, todos com coordenadas inteiras e sem pontos repetidos, a tua tarefa é calcular o número de quadrados que se podem formar usando apenas esses pontos. Dentro desses quadrados, tens também de calcular qual é a área do maior, no caso de haver pelo menos um quadrado.

Restrições:
1 ≤ N ≤ 3 000       Número de pontos a considerar
1 ≤ Xi, Yi ≤ 20 000       Coordenadas dos pontos

Nota Inicial:
Todas as soluções deste problema passam por enumerar de alguma maneira todos os quadrados existentes. Sendo assim, para calcular a área do maior quadrado basta calcular a área de cada quadrado que se enumera (usando as coordenadas dos pontos do quadrado, calculando a distância entre dois pontos que formem um dos lados e tomando o seu quadrado). Sendo assim vamos apenas descrever a operação de enumerar todos os quadrados e a operação de calcular a área fica assumida como trivial.

Solução base:
A primeira parte para resolver este problema passa por perceber como perceber que quatro pontos são um quadrado. A ideia desta solução é então considerar cada conjunto de quatro pontos (com 4 loops encadeados) e saber se esse conjunto forma ou não um quadrado. Notem que não basta ver se a figura formada tem os lados são iguais, logo num dos casos de exemplo temos conjuntos de 4 pontos que formam um losângulo que tem os 4 lados iguais, mas que não é um quadrado.

Podemos fazer esta verificação de várias maneiras, todas elas um pouco geométricas. Uma primeira seria considerar o teorema de pitágoras e assim verificar se o quadrado da diagonal é igual a duas vezes o quadrado do lado da figura. Caso seja, temos um quadrado. Outra maneira seria além de verificar que os 4 lados são iguais, verificar também que os 4 ângulos são iguais, podendo fazer isto utilizando vetores e a noção de produto escalar por exemplo (que inclui a noção trignométrica de senos e cosenos). Finalmente, talvez a mais simples seria simplesmente verificar que o comprimento das duas diagonais da figura são iguais. Caso seja, novamente, quadrado!

Temos assim uma maneira de exaustivamente verificar quantos conjuntos de 4 pontos formam quadrados.

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

Solução Quase-Ótima:
Para melhorar a solução anterior temos de pensar qual o mínimo de informação que precisamos para definir um quadrado. Claramente se apenas tivermos um ponto não conseguimos definir um só quadrado, visto que podemos ter imensos quadrados que incluam aquele ponto (basta variar o comprimento dos lados). Com dois pontos já só temos dois possíveis quadrados que incluam esses dois pontos. A imagem seguinte ilustra essa situação (os dois pontos escolhidos estão a vermelho e a preto os dois quadrados).

Sendo assim, vamos pegar em cada par de pontos e ver se conseguimos formar um dos quadrados como na imagem acima. Só precisamos de um porque ao considerarmos todos os pares, caso um dos quadrados exista vamos considerar os 4 pares de pontos que formam os seus lados, o que se procurássemos pelos dois quadrados íamos contar cada quadrado 4 vezes (uma por cada um dos 4 pares). Sendo assim, basta-nos para cada par de pontos escolher um dos quadrados, calcular as coordenadas dos outros dois pontos e verificar se ambos estão na nossa lista de N pontos.

Para calcular as coordenadas dos outros dois pontos podíamos usar várias abordagens. A primeira seria usar trigonometria, o que para quem está habituado seria muito fácil, mas caso contrário não seria assim tão fácil. Outra alternativa seria pensar um pouco como manipular as coordenadas de cada ponto. Vejamos a imagem seguinte para perceber melhor isto.

Na imagem anterior, o segmento a vermelho seria o equivalente ao segmento gerado pelo par de pontos que estamos a considerar, sendo esses pontos os pontos marcados como 'A' e 'B'. Cada segmento etiquetado por x e y tem o mesmo comprimento e x = B.x - A.x, e y = A.y - B.y. Agora a ideia é ir "rodando" os pontos usando o esquema da figura. Somando x à coordenada y do ponto B e y à coordenada x obtemos as coordenadas do ponto D. De maneira análoga, subtraindo x à coordenada x do ponto D e somando y à coordenada y obtemos as coordenadas do ponto C. Agora que já temos as coordenadas dos outros dois pontos, basta verificar se estão na nossa lista de pontos. Já agora, também era possível fazer estes cálculos usando vetores, que dariam contas um pouco mais complicadas, mas nada de especial.

Para saber se os pontos estão na nossa lista temos várias alternativas. A primeira e mais simples, passaria por fazer uma pesquisa linear pela lista de pontos, ou seja, comparar as coordenadas cada ponto da lista com as de C e D. Assim, por cada par de pontos fazemos uma pesquisa em O(N) e encontraríamos todos os retângulos.

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

Solução Quase-Quase-Ótima:
Para melhorar a solução temos de descer o fator linear para, por exemplo logarítmico. A já conhecida pesquisa binária parece ser um exemplo de algo que funcionaria, mas não nos podemos esquecer que estamos a trabalhar com pontos, ou seja, elementos em 2D. Existem estruturas de dados que fazem estas operações eficientemente, mas a maior parte é bastante complexa e ainda mais complexa para implementar. Porém, neste caso em específico podíamos reparar que o valor máximo para cada coordenada é de 20,000 logo podemos "concatenar" o valor de cada coordenada para obter um único inteiro que representa cada ponto. A ideia é multiplicar a coordenada y por 100,000 e somar-lhe o valor da coordenada x. Por exemplo se tivéssemos o ponto (90, 120) representá-lo-iamos por 12,000,090. Notem que o valor máximo possível, 2,000,020,000 cabe num inteiro (mas não por muito). Sendo assim já seria possível guardar cada ponto numa lista ordenada e fazer uma pesquisa binária para verificar se ele existe.

Uma maneira alternativa de conseguir uma complexidade semelhante seria usar por exemplo um map da STL. Podíamos usá-lo com inteiros como no parágrafo anterior, ou usar por exemplo pairs da STL.

Esta seria uma solução O(N^2 * log(V)) que daria aproximadamente 80 pontos.

Solução Ótima:
Este problema tinha casos de teste e limites apertados mesmo para poder diferenciar as várias soluções. Num recente artigo do Loop menciona-se que é raro existir um problema onde uma solução O(N) passe mas O(N * log(N)) não. Bom, este é um desses problemas raros. Vamos então melhorá-lo.

Podemos retirar o fator logaritmo de várias maneiras. Uma muito interessante seria reparar que 2,000,020,000 bits são "apenas" 250 MB (mais coisa menos coisa). Logo, visto que a memória máxima global para este problema era de 256 MB, se explorássemos bem os conjuntos de dados que temos, conseguíamos guardar um bit para cada um dos possíveis 2,000,020,000 indicando se esse ponto existiria ou não (podiamos melhorar isto ainda mais visto que números como o 1,000,090,000 não são possíveis). Uma possível abordagem seria guardar um conjunto de 2,000,020,000 / 32 inteiros (cada inteiro tem 32 bits) e com alguma matemática descobrir onde está cada inteiro e com operações bitwise manipular os vários bits. Uma alternativa mais "preguiçosa" seria usar por exemplo bitsets da STL, que faz precisamente isto que referimos.

Uma outra solução seria usar uma trie, que funciona como uma árvore onde cada nó representa um dígito e uma pesquisa passa por percorrer essa árvore pelos dígitos respetivos (usando a técnica do primeiro parágrafo desta secção) e se for possível percorrer esse caminho e chegarmos a um nó que esteja marcado como final, temos um ponto. Notem que em teoria esta solução tem um fator igual ao número de dígitos adicional à complexidade, que equivale a um logaritmo de base 10, mas como para o valor máximo o seu logaritmo de base 10 é tão pequeno, vamos considerar que não é introduzido nenhum fator.

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

Ligações interessantes: