A Alice adora
todo o tipo de jogos e ainda ontem o Bernardo, um grande amigo, lhe
propôs um novo desafio geométrico. Inicialmente, a Alice tem
disponível uma folha de papel quadriculado com um conjunto de pontos
lá desenhados, sendo que os pontos estão sempre em vértices do
quadriculado. Um exemplo seriam os seguintes 9 pontos:
O desafio é desenhar todos os quadrados cujos vértices pertencem ao conjunto de pontos dado. Recorda que um quadrado é um quadrilátero regular, ou seja, uma figura geométrica com quatro lados de igual comprimento e quatro ângulos rectos. Inicialmente, a Alice conseguiu ver apenas um quadrado:
Contudo, o Bernardo fez notar que os quadrados podem estar em qualquer orientação, não tendo de estar alinhados com os eixos do papel quadriculado. A Alice pensou, pensou, e descobriu que afinal conseguia desenhar 3 quadrados diferentes:
De entre todos os possíveis quadrados, o Bernardo quer que a Alice descubra qual tem maior área. Recorda que a área de um quadrado de lado L é igual a L vezes L. Por exemplo, para a figura anterior, o quadrado de maior área é o verde, com área 5. O quadrado vermelho tem área 4 e o quadrado azul tem área 2.
Consegues ajudar a Alice a superar este desafio, seja qual for o conjunto de pontos?
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.
Na primeira linha vem um número inteiro N, representando o número de pontos.
Em cada uma das N linhas seguintes vem um par de números inteiros Xi Yi (separados por um espaço), indicando que o i-ésimo ponto tem coordenadas (Xi,Yi). Os pontos podem vir por qualquer ordem e é garantido que não existem dois pontos com as mesmas coordenadas.
Na primeira linha de output deve vir um número inteiro, indicando o número de quadrados que é possível formar com os pontos dados. Caso exista pelo menos um quadrado, deve existir uma segunda linha no output com um número inteiro indicando qual a maior área, ou seja, dentro dos quadrados que é possível formar, qual é a área máxima.
Nota que os quadrados podem estar uns por cima dos outros.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ N ≤ 3 000 | Número de pontos a considerar | |
1 ≤ Xi, Yi ≤ 20 000 | Coordenadas dos pontos |
Para um conjunto de casos de teste valendo 25% dos pontos, acontece sempre que todos os quadrados existentes estão alinhados com os eixos vertical e horizontal e além disso N ≤ 50.
Para um conjunto de casos de teste valendo 50% dos pontos, os quadrados podem ter qualquer orientação, mas N ≤ 50.
9 5 3 1 4 1 3 1 2 2 1 2 3 3 4 3 2 4 2
3 5
Corresponde à figura dada atrás no enunciado.
6 1 1 1 2 1 3 2 3 2 2 2 1
2 1
Corresponde à figura seguinte, com dois quadrados e cuja maior área é 1:
3 1 1 1 2 2 1
0
Não é possível formar nenhum quadrado.