Trójmiasto
Limit pamięci: 128 MB
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.
Wejście
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 .
Wyjście
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.
Przykład
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.