Imagine que as coordenadas ( x, y ) de n pontos são armazenadas nos vetores x e y do tipo int. Imagine um valor de raio r do tipo int. Escrever um programa para determinar qual é o ponto ( x, y ) que corresponde ao centro de um círculo de raio r que contém mais pontos dentre os n pontos dados. Lembrar que a distância entre os pontos com coordenadas (a, b) e (c, d) é dada por raiz(a-c)^2+(b-d)^2.

Passo 1

O enunciado pede para, dado um conjunto de n pontos de coordenadas inteiras armazenadas nos vetores x[] e y[] e um raio inteiro r, achar o ponto (x, y) que, se usado como centro de um círculo de raio r, contém o maior número desses n pontos. O conteúdo aqui é simples força bruta combinada com cálculo de distância euclidiana.

Passo 2

Percorrer cada ponto i (i de 0 até n–1) como candidato a centro do círculo. Para cada i, inicializar um contador cnt=0.
Para um dado centro i, percorrer todos os pontos j (j de 0 até n–1) e calcular a distância de i a j usando a fórmula raiz(x[i]-x[j])^2 + (y[i]-y[j])^2. Se essa distância for menor ou igual a r, incrementar cnt.

Passo 3

Manter duas variáveis: bestCount (maior cnt já visto) e bestIndex (índice do ponto que gerou bestCount). Sempre que cnt ultrapassar bestCount, atualizar bestCount=cnt e bestIndex=i.
Ao final, o ponto de índice bestIndex, ou seja (x[bestIndex], y[bestIndex]), é o centro que contém o maior número de pontos dentro do círculo de raio r.

Resposta

O ponto (x[bestIndex], y[bestIndex]), onde bestIndex é o índice que maximiza a quantidade de pontos dentro do círculo de raio r, é a resposta.

Exercícios relacionados