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.