| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
DDZ2025_4 - Manhatan1 |
Zadanie 4: Punkt minimalizujący sumę odległości (metryka Manhattan)
W mieście Gridland organizowany jest nowy system dystrybucji posiłków dronami. Centralne centrum logistyczne chce wybrać takie miejsce (X*, Y*), aby suma odległości od tego miejsca do wszystkich klientów była możliwie najmniejsza, licząc w metryce Manhattan. Podpowiedź: optymalną współrzędną w każdej osi (X i Y) stanowi mediana wszystkich współrzędnych klientów. Mediana to środkowy element w zbiorze uporządkowanym.
Metryka Manhattan odległości punktów
(x₁, y₁) i (x₂, y₂) to
|x₁ − x₂| + |y₁ − y₂|. Twoim zadaniem jest obliczyć tę minimalną sumaryczną
odległość do wszystkich klientów i wypisać jedynie tę wartość.
Wejście
Pierwsza linia zawiera liczbę całkowitą n (1 ≤ n ≤ 200 000) – liczbę klientów.
Kolejna linia zawiera n par współrzędnych
xᵢ yᵢ (−109 ≤ xᵢ, yᵢ ≤ 109), rozdzielone spacjami.
Wyjście
Jedna liczba całkowita – minimalna możliwa suma odległości Manhattan od wybranego punktu do wszystkich klientów.
Przykład
Wejście:
5
1 2
3 0
-1 1
0 -2
2 2
Wyjście:
12
Wyjaśnienie: mediana X to 1, mediana Y to 1; suma odległości = |1−1|+|2−1| + |3−1|+|0−1| + … = 12.
| Dodane przez: | Marcin Kasprowicz |
| Data dodania: | 2025-06-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 COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET |
RSS