sexta-feira, 26 de outubro de 2012

[Maratona de Programação] Problema Pontos

Olá pessoal, nesse post iremos ver a solução para o problema Pontos cujo código no SPOJ é PARPROX. Esse problema é do Treino pra OBI (Olimpíada Brasileira de Informática) 2006. É o problema do par mais próximo (closet pair problem).

Link do problema no SPOJ: http://br.spoj.pl/problems/PARPROX/

É sempre bom tentar resolver o problema antes de ver a solução. Caso você tenha tentado e ainda assim não conseguiu, clique aqui para ver uma dica de como resolver esse problema. Se, mesmo com essa dica, você não conseguir resolvê-lo, então clique em "Continue lendo...".

Código:
(clique na imagem para vê-la em tamanho maior)


Linhas 3 a 5: inclusão das bibliotecas.

Linha 11: declaração de variáveis. N indica o número de pontos a serem considerados. X e Y representam as coordenadas de cada ponto. As variáveis i e j são usadas nos comandos de repetição "for".

Linha 12: declaração de vetores. O vetor vetX irá guardar as coordenadas X e vetY irá guardar as coordenadas Y.

Linha 13: declaração da variável D que irá guardar a distância entre dois pontos. A variável menorD irá armazenar a menor distância.

Linha 15: scanf é uma função de entrada de dados. Nesse caso ela irá guardar o número de pontos na variável N.

Linha 16: um "for" de i = 0 até i < N é feito para pegar as coordenadas (X e Y) de todos os pontos.

Linha 18: pego valor das coordenadas X e Y do ponto.

Linha 19: guardo a coordenada X em vetX. A função push_back é uma função para inserir um elemento no vetor.

Linha 20: guardo a coordenada Y em vetY.

A distância entre dois pontos do plano é calculada utilizando a seguinte fórmula:


Linha 22: menorD recebe o cálculo da primeira distância entre dois pontos. sqrt é uma função da biblioteca math.h para calcular a raiz quadrada. A função pow também é da math.h, ela serve para calcular a exponenciação. Veja que eu utilizo essas funções para implementar a fórmula da distância entre dois pontos que eu acabei de colocar.

A ideia é calcular a distância entre cada par de pontos e guardar a menor distância encontrada até o momento. Logo abaixo temos o algoritmo para resolver o problema do par mais próximo:


E é a partir da linha 23 que implementamos o algoritmo acima. A única diferença é que no algoritmo o "i" começa em 2 e o "j" começa em 1 (linhas 2 e 3 do algoritmo). Como o nosso vetor começa da posição 0, então eu fiz a alteração apropriada, ou seja, o nosso "i" irá começar em 1 e o "j" em 0. Assim eu poderei calcular a distância entre todos os pontos e ver quem é a menor.

Linha 23: temos um "for" que imita a linha 2 do algoritmo, sendo que a única diferença é que o nosso "i" é inicializado com 1 pelo fato já discutido anteriormente.

Linha 25: temos um "for" dentro de outro "for" que imita o que acontece na linha 3 do algoritmo, sendo que a única diferença é que o nosso "j" começa em 0. Um "for" dentro do outro permite calcularmos a distância entre todos os pontos.

Linha 27: D recebe o cálculo da distância entre dois pontos.

Linha 28: verifico se a distância D é menor que a distância menorD, se for então menorD recebe D.

Linha 32: mostro a menor distância (menorD). "lf" é o especificador de formato para mostrar variáveis do tipo double. O ".3" é para mostrar com precisão na terceira casa decimal (é uma exigência do problema).


Nenhum comentário: