Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_03_14 - Metryka miasto |
Metryka miasto
Bitek odpowiedzialny jest za organizację spotkań członków Ochotniczej Straży Binarnej w Bitogrodzie. Za każdym razem kiedy chce zorganizować spotkanie, wysyła do wszystkich członków SMS, a każdy członek zainteresowany spotkaniem odpowiada Bitkowi, wysyłając swoje koordynaty najbliższego skrzyżowania. Ulice w mieście tworzą siatkę, po której można poruszać się w metryce miasto, a punkty kratowe tej siatki są skrzyżowaniami. Na podstawie przesłanych koordynatów, Bitek wybiera na spotkanie takie skrzyżowanie, aby zminimalizować sumę odległości przebytą przez członków OSB. Twoim zadaniem jest wyznaczenie tej sumy.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (0 < d < 100) oznaczająca liczbę zestawów danych. W kolejnych wierszach znajdują się zestawy danych. Pierwszy wiersz każdego zestawu to liczba całkowita n (0 < n < 1000) oznaczająca liczbę zainteresowanych spotkaniem członków OSB. W kolejnych n wierszach podane są po dwie liczby całkowite, x, y (0 ≤ x, y ≤ 106) oznaczające koordynaty skrzyżowań wysłane przez członków OSB.
Wyjście
Dla każdego zestawu należy wyznaczyć sumę odległości przebytą przez członków OSB do wyznaczonego przez Bitka skrzyżowania.
Przykład
Wejście
2
5
0 0
2 0
1 1
0 3
2 3
4
2 2
2 2
5 1
5 2
Wyjście
10
7
Dodane przez: | Mariusz Śliwiński |
Data dodania: | 2015-03-08 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |