{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"As capivaras da UFV adoram doce de leite Viçosa. Como elas estavam ficando muito gordas, os funcionários da universidade decidiram tratar delas espalhando doce em vários locais do campus, de forma a fazer com que elas andem muito para comer. Como elas são muito sedentárias, te contrataram para criar um programa capaz de planejar a melhor rota que elas devem seguir com o objetivo de comerem todo o doce.\n\nAssuma que a UFV seja uma grade com coordenadas inteiras. Você deverá direcionar as capivaras para as coordenadas de cada doce. \n\nNessa versão inicial do seu sistema, o objetivo será calcular o custo da menor rota que as capivaras devem seguir de modo a coletar todo o doce e voltar para a posição inicial (um ninho localizado em uma das lagoas).\n\nComo as capivaras ainda não cursaram GAAL, não sabem que andar nas diagonais é mais vantajoso. Assim, elas só conseguem se mover da posição $(i,j)$ para as posições $(i-1,j)$, $(i,j+1)$, $(i,j-1)$ e $(i+1,j)$ - cada movimento tem distância $1$. A grade representando a UFV possui no máximo $20 \\times 20$ células/quarteirões. Para evitar que as roedoras engordem, os funcionários colocam no máximo 10 doces espalhados pela universidade. \n\nCada coordenada será dada como um par $(x,y)$ onde cada valor estará entre 1 e o tamanho da grade na direção correspondente."}},{"title":"Entrada","value":{"format":"MD","content":"A entrada contém vários casos de teste. A primeira linha contém um inteiro representando a quantidade de casos de teste. Para cada caso, a primeira linha contém dois inteiros $N$ e $M$ representando as dimensões da grade da UFV. A próxima linha contém dois inteiros $C_x$ e $C_y$ representando as coordenadas $(C_x,C_y)$ do ninho das capivaras. Então, em uma linha temos a quantidade $N$ de doces espalhados pelo campus. Finalmente, há $N$ linhas, cada uma contendo as coordenadas $(x,y)$ de um doce. "}},{"title":"Saída","value":{"format":"MD","content":"Para cada caso de teste escreva uma linha informando o valor da distância total mínima que as capivaras terão que percorrer de modo a sair do ninho, coletar todo o doce e voltar para a posição inicial. Siga o formato do exemplo."}},{"title":"Exemplo","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eEntrada\u003c/th\u003e\n \u003cth\u003eSaída\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\n1\n10 10\n1 1\n4\n2 3\n5 5\n9 4\n6 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\nThe shortest path has length 24\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}