Problema 1: Piso

Arquivo: piso.c ou piso.pas
Entrada: piso.in
Saída: piso.out

Uma empresa que trabalha com instalação de pisos, freqüentemente precisa aplainar o cimento sobre o qual as peças são colocadas. Esta tarefa pode ser feita com auxílio de um tipo de prensa pesada e de difícil deslocamento. Várias pessoas trabalham na instalação de um piso e, durante esse serviço, algumas delas necessitam de uma destas prensas para fazer um algum ajuste na instalação de um dos azulejos. Quando uma pessoa necessita de uma prensa, uma delas é levada à posição onde a pessoa está. Obviamente, enquanto a prensa não chega, o trabalhador está parado, esperando.

Na tentativa de minimizar o tempo de espera dos trabalhadores, a empresa pensou em uma regra de controle do movimento das prensa. A regra consiste no seguinte. Para cada requisição do uso de uma prensa, a que está mais próxima ao ponto de requisição é escolhida para ser levada. Cada prensa é identificada por um número de 1 a $k$ e, em caso de haver duas prensas à mesma distância do trabalhador que fez a requisição, a prensa de número menor é escolhida para ser levada. Após usar a prensa esta é deixada nesta posição, esperando uma possível nova requisição para então ser transportada.

Você deve escrever um programa que recebe o número $k$ de prensas, a posição inicial de cada uma delas e uma sequência de requisições. Seu programa deve calcular a distância total percorrida pelas prensas para atender a estas requisições de acordo com a regra descrita acima.

Uma posição inicial consiste de um par $(x,y)$ de números reais, indicando um ponto no plano. Uma requisição também consiste de um par $(x,y)$ de números reais, para onde uma prensa deve ser levada.