Problema B - Desenhando Quadrados

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?

O 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.

Input

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.

Output

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.

Restrições

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

Nota sobre a avaliação

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.

Exemplo de Input 1

9
5 3
1 4
1 3
1 2
2 1
2 3
3 4
3 2
4 2

Exemplo de Output 1

3
5

Explicação do Input/Output 1

Corresponde à figura dada atrás no enunciado.

Exemplo de Input 2

6
1 1
1 2
1 3
2 3
2 2
2 1

Exemplo de Output 2

2
1

Explicação do Input/Output 2

Corresponde à figura seguinte, com dois quadrados e cuja maior área é 1:

Exemplo de Input 3

3
1 1
1 2
2 1

Exemplo de Output 3

0

Explicação do Input/Output 3

Não é possível formar nenhum quadrado.


Qualificação para a final das ONI'2014
(23/04 a 25/04 de 2014)