beecrowd 1137 · circuncentro

Pontos Cocirculares

Encontrar a maior quantidade de pontos que pode pertencer à mesma circunferência.

triplas + verificação

Três pontos determinam o candidato

Três pontos não colineares determinam uma única circunferência. Portanto, testamos cada combinação de três pontos, construímos seu circuncírculo e contamos quantos dos outros pontos têm o mesmo raio em relação ao centro encontrado.

Geometricamente, o centro é a interseção de duas mediatrizes. No código, a fórmula em coordenadas evita representar retas verticais e horizontais como casos especiais.

Triângulo inscrito, suas mediatrizes e cinco pontos cocirculares
Diagrama criado para a aula: o circuncentro é equidistante dos pontos da circunferência.

O determinante detecta degeneração

D = 2[x₁(y₂-y₃) + x₂(y₃-y₁) + x₃(y₁-y₂)]

Quando D = 0, a área orientada do triângulo também é zero: os três pontos são colineares e não existe um círculo finito único passando por eles. Esse trio deve ser ignorado.

Como o centro e o raio usam ponto flutuante, não compare distâncias com ==. A solução usa math.isclose com tolerâncias relativa e absoluta.

Busca por circunferências

Trio selecionado
Neste círculo
Melhor resposta
iCombinação em análise

Complexidade e contagem

Existem O(N³) trios e, para cada um, podemos examinar até O(N) pontos. Com no máximo 100 pontos e o limite generoso citado no material, a abordagem direta é suficiente.

Por que o laço pode começar em k + 1? Para qualquer círculo ótimo, o trio formado pelos seus três menores índices será testado; todos os outros pontos desse círculo aparecem depois de k.
Construção do candidatoAbrir 1137.py
import math
import sys


EPSILON = 1e-7


def circuncirculo(a, b, c):
    # Três pontos não colineares determinam um único círculo.
    ax, ay = a
    bx, by = b
    cx, cy = c
    determinante = 2.0 * (
        ax * (by - cy) + bx * (cy - ay) + cx * (ay - by)
    )

    # Determinante zero significa que os pontos são colineares.
    if math.isclose(determinante, 0.0, abs_tol=EPSILON):
        return None

    a2 = ax * ax + ay * ay
    b2 = bx * bx + by * by
    c2 = cx * cx + cy * cy
    centro_x = (
        a2 * (by - cy) + b2 * (cy - ay) + c2 * (ay - by)
    ) / determinante
    centro_y = (
        a2 * (cx - bx) + b2 * (ax - cx) + c2 * (bx - ax)
    ) / determinante

    # Guardamos r² para comparar sem calcular raízes.
    raio_2 = (ax - centro_x) ** 2 + (ay - centro_y) ** 2
    return centro_x, centro_y, raio_2


def esta_no_circulo(ponto, circulo):
    x, y = ponto
    centro_x, centro_y, raio_2 = circulo
    distancia_2 = (x - centro_x) ** 2 + (y - centro_y) ** 2

    # A tolerância absorve pequenos erros de ponto flutuante.
    return math.isclose(
        distancia_2, raio_2, rel_tol=EPSILON, abs_tol=EPSILON
    )


def maior_quantidade_cocircular(pontos):
    quantidade = len(pontos)
    if quantidade <= 2:
        return quantidade

    melhor = 2
    # Enumeramos todos os trios capazes de definir um círculo candidato.
    for i in range(quantidade):
        for j in range(i + 1, quantidade):
            for k in range(j + 1, quantidade):
                circulo = circuncirculo(pontos[i], pontos[j], pontos[k])
                if circulo is None:
                    continue

                atual = 3  # Os pontos i, j e k já pertencem ao círculo.
                for m in range(k + 1, quantidade):
                    if esta_no_circulo(pontos[m], circulo):
                        atual += 1
                melhor = max(melhor, atual)

    return melhor


def main():
    dados = iter(sys.stdin.buffer.read().split())
    respostas = []

    for token in dados:
        quantidade = int(token)
        if quantidade == 0:
            break

        pontos = [
            (float(next(dados)), float(next(dados)))
            for _ in range(quantidade)
        ]
        respostas.append(str(maior_quantidade_cocircular(pontos)))

    sys.stdout.write("\n".join(respostas) + "\n")


if __name__ == "__main__":
    main()

Fontes e validação