Question

uri 2046 - Entregadores de steak
O Texas é famoso pela sua carne de excelente qualidade. “Steaks” com até dois centímetros de espessura assados em churrasqueiras são a especialidade culinária do estado. Em San Antonio é difícil encontrar entregadores de pizza por telefone, mas é muito comum encontrar “disk steaks”. Você liga para o número e em poucos minutos chega um suculento bife à sua casa, quente e pronto para comer. É claro que tamanha eficiência depende de um complicado sistema de entregas. Há várias sedes da empresa espalhadas pela cidade, e sempre que uma chamada é feita a sede mais próxima é acionada, o steak é assado e o entregador segue com o suculento jantar. Sabemos que San Antonio é uma cidade planejada. Podemos imaginar os cruzamentos da cidade como vértices de uma grade. Por algum motivo obscuro, todas as sedes estão instaladas em cruzamentos. Sua tarefa é ajudar a empresa na entrega dos steaks.

Entrada

São dadas várias instâncias. Para cada instância são dadas as dimensões 0 ≤ M, N ≤ 1000 da cidade (será uma grade com M linhas e N colunas). Um valor N = 0 ou M = 0 indica o fim dos dados. A seguir vem o número 0 < K ≤ 100000 de sedes da empresa. Nas Klinhas seguintes vêm as coordenadas das sedes. A seguir, vem o número 0 ≤ L ≤ 100000 de ligações pedindo steaks. Nas L linhas seguintes vêm as coordenadas da posição de cada chamada (que também são vértices da grade).

Saída

Para cada instância solucionada, você deverá imprimir um identificador Instancia H em que H é um número inteiro, seqüencial e crescente a partir de 1. Nas L linhas seguintes, você deve imprimir por qual sede da empresa o pedido correspondente àquela linha foi atendido. Em caso de haver mais de uma sede à mesma distância, dê preferência pela que possuir menor índice de linha. Persistindo o empate, dê preferência pela com menor índice de coluna. Uma linha em branco deve separar a saída de cada instância.

Exemplo de EntradaExemplo de Saída

3 3

2

1 1

1 3

2

2 1

2 3

0 0

Instancia 1

1 1

1 3

IX Maratona de Programação IME-USP, 2005

Answer 1

Não dá para apresentar o programa completo aqui. A estrategia é entrar com os valores x e y das sedes em um vetor, e para cada pedido calcular a distancia ( distancia de Manhattan) para cada sede, anotando a que for menor. Lembrar que na comparação de distancias, se uma for igual a outra, a menor será aquela com menor valor de x, e se os x forem iguais, aquela que tiver o menor y.