W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W Bajtocji jest miast, których położenie możemy przedstawić w postaci punktów na płaszczyźnie o całkowitych współrzędnych. Odległość między dwoma miastami o współrzędnych i jest określona w standardowy sposób: .
Król Bajtocji, Bajtazar, chce wyznaczyć trzy miasta, które połączy i zamieni w Trójmiasto (wzorem pewnego egzotycznego królestwa, w którym w Trójmieście odbywają się finały tamtejszej OI oraz rozmaitych międzynarodowych zawodów programistycznych). Bajtazar postanowił wybrać takie trzy miasta, dla których suma odległości pomiędzy każdymi dwoma z nich jest minimalna.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę miast w Bajtocji. Miasta są ponumerowane od 1 do . W kolejnych wierszach znajdują się po dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające współrzędne -tego wierzchołka miasta.
Możesz założyć, że w testach wartych łącznie punktów zachodzi dodatkowy warunek , a w testach wartych łącznie punktów zachodzi .
Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę, równą minimalnej sumie odległości pomiędzy miastami wybranego Trójmiasta, zapisaną z dokładnością do dwóch miejsc po przecinku.
Dla danych wejściowych:
5 0 0 0 3 0 8 4 0 5 4
poprawną odpowiedzią jest:
12.00
Wyjaśnienie do przykładu: Bajtazar wybierze miasta: 1, 2 i 4.
Autor zadania: Jacek Tomasiewicz.