Desafio: Pontos Inteiros em Posição Geral

Escolher pontos com coordenadas inteiras é fácil. Fazer com que todas as distâncias entre eles também sejam inteiras já exige algum trabalho.

Agora acrescente duas condições: nenhuma reta pode conter três desses pontos, e nenhuma circunferência pode conter quatro.

Quantos pontos você consegue encontrar?

O desafio

Escreva um programa que receba um inteiro $n \geq 4$ (idealmente para $n \geq 8$) e tente construir um conjunto de $n$ pontos distintos no plano:

$$ S = {P_1, P_2, \ldots, P_n}, \qquad P_i = (x_i, y_i). $$

O conjunto deve satisfazer simultaneamente as quatro condições abaixo.

1. Coordenadas inteiras

Cada ponto deve ter coordenadas inteiras:

$$ x_i, y_i \in \mathbb{Z}. $$

Coordenadas negativas e iguais a zero são permitidas.

2. Distâncias inteiras

A distância euclidiana entre quaisquer dois pontos distintos deve ser um inteiro positivo:

$$ d(P_i, P_j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \in \mathbb{Z}_{>0}. $$

Essa condição vale para todos os pares, incluindo pontos que não sejam vizinhos em uma eventual representação como polígono.

3. Nenhuma trinca colinear

Não podem existir três pontos distintos pertencentes à mesma reta.

4. Nenhuma quádrupla concíclica

Não podem existir quatro pontos distintos pertencentes à mesma circunferência.

A restrição vale para qualquer grupo de quatro pontos, mesmo que o restante do conjunto esteja fora dessa circunferência.

Exemplo válido

Para $n=4$, uma solução é:

0 0
3 4
6 0
3 -4

As seis distâncias são:

Nenhuma trinca é colinear.

Os quatro pontos também não são concíclicos: um centro equidistante de $P_1$ e $P_3$ deve ter $x=3$, enquanto um centro equidistante de $P_2$ e $P_4$ deve ter $y=0$. O único centro possível seria $(3,0)$, mas as distâncias desse centro aos pontos são 3 e 4.

Entrada e saída

Seu programa deve receber a quantidade desejada de pontos:

4

Caso encontre uma solução, deve informar os pontos e o resultado de uma verificação independente:

Status: solução encontrada
Quantidade: 4

0 0
3 4
6 0
3 -4

Coordenadas inteiras: sim
Pontos distintos: sim
Distâncias inteiras: sim
Nenhuma trinca colinear: sim
Nenhuma quádrupla concíclica: sim
Conjunto válido: sim

Você pode adicionar parâmetros como limite das coordenadas, tempo máximo de execução e semente aleatória.

Se a busca terminar sem alcançar o objetivo, informe isso explicitamente:

Status: tempo máximo atingido
Quantidade solicitada: 5
Quantidade encontrada: 4
Conjunto parcial válido: sim

Não encontrar uma solução não demonstra que ela seja impossível.

Implemente também uma verificadora

Além do gerador, escreva uma função que receba um conjunto de pontos e confira todas as condições.

A verificadora deve funcionar inclusive para conjuntos fornecidos manualmente, sem depender de informações internas do gerador.

Algumas dicas para evitar erros numéricos:

• Para verificar distâncias, teste se a distância ao quadrado é um quadrado perfeito.
• Para verificar colinearidade, use o determinante que representa o dobro da área do triângulo.
• Para verificar conciclicidade, use um determinante com as coordenadas dos quatro pontos.
• Utilize inteiros com precisão suficiente para evitar overflow.

Para quatro pontos, o teste de conciclicidade utiliza:

$$ \begin{vmatrix} x_1 & y_1 & x_1^2+y_1^2 & 1 \\ x_2 & y_2 & x_2^2+y_2^2 & 1 \\ x_3 & y_3 & x_3^2+y_3^2 & 1 \\ x_4 & y_4 & x_4^2+y_4^2 & 1 \end{vmatrix} = 0. $$

Depois de excluir trincas colineares, um determinante nulo indica quatro pontos concíclicos.

Como comparar as soluções

Ao apresentar sua implementação, registre:

• Quantidade de pontos encontrados.
• Maior valor absoluto entre as coordenadas.
• Tempo de construção e tempo de verificação, separadamente.
• Estratégia de busca e parâmetros utilizados.
• Código e instruções para reproduzir o resultado.

O objetivo principal é encontrar conjuntos válidos maiores. Para conjuntos do mesmo tamanho, coordenadas menores e menor tempo de execução são critérios adicionais interessantes.

Sua solução é capaz de computar um conjunto com mais de 7 pontos?