F-Crown

Pak udin meninggalkan rumahnya jam 6 pagi untuk memerah sapi di peternakannya. Namun, sehari sebelumnya ada hujan lebat yang menyebabkan padang rumput menjadi berlumpur. Pak Udin berangkat dari titik (0, 0) dan bergerak ke arah kandang sapi yang berada di (x, y) (-500 <= x <= 500); (-500 <= y <= 500).
Pak Udin dapat melihat semua N (1 <= N <= 100) kubangan lumpur yang ada di titik (a,b), -500 <= a <= 500); (-500 <= b <= 500) yang terdapat di padang rumput. Setiap kubangan hanya menempati sebuah titik saja. Karena pak Udin baru saja membeli sepatu boot baru, dia tidak ingin mengotori sepatu karena terperosok ke salah satu kubangan, tapi juga ingin mencapai kandang sapinya secepat mungkin. Jika Pak Udin hanya dapat bergarak secara paralel (sejajar) terhadap sumbu yang ada dan bebelok pada titik dengan koordinat bilangan bulat, berapakah jarak terdekat yang harus dilalui untuk mencapai kandang sapinya tanpa mengotori sepatunya? Dijamin selalu ada cara untuk mencapai kandang sapi tanpa mengotori sepatu pak Udin.
FORMAT INPUT:
Baris pertama input berupa sebuah bilangan integer K yang menunjukkan jumlah kasus yang harus dikerjakan. Selanjutnya, untuk tiap kasus akan berisi:
Baris 1 : tiga bilangan bulat dipisahkan spasi: x, y, dan n
Baris 2.n+i : dua bilangan bulat dipisahkan spasi: ai dan bi
FORMAT OUTPUT
Untuk tiap kasus akan berisi:
Baris 1 : jarak minimum yang harus ditempuh pak Udin untuk mencapai kandang sapi tanpa mengotori sepatunya.

CONTOH INPUT:
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
Kandang sapi ada di posisi (1, 2). Pak Udin melihat 7 kubangan pada posisi (0, 2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1) dan (2, 2).
4 . . . . . . . .
3 . M . . . . . . M = Kubangan Lumpur
Y 2 . . M S M . M . S = Kandang Sapi
1 . M . M . M . . * = Pak Udin
0 . . * . . . . .
-1 . . . . . . . .
-2 -1 0 1 2 3 4 5
X
CONTOH OUTPUT
11
PEMBAHASAN:
Rute terbaik bagi pak udin adalah (0, 0) (-1, 0); (-2, 0); (-2, 1); (-2, 2); (-2, 3); (-2, 4); (-1, 4); (0, 4); (0, 3); (1, 3); dan (1,2).
4 * * * . . . . .
3 * M * * . . . . M = Kubangan Lumpur
Y 2 * . M S M . M . S = Kandang Sapi
1 * M . M . M . . * = Pak Udin
0 * * * . . . . .
-1 . . . . . . . .
-2 -1 0 1 2 3 4 5
X
Jadi yang harus dileswati pak udin sebanyak 11 langkah, sesuai dengan jumlah * pada gambar diatas.
 Klo Mau Tahu Source Codenya Klik Disini

Sumber NPC..