Limit pamięci: 32MB
W Stasziclandii odbywają się mistrzostwa w programowaniu. Jest to wydarzenie tak niezwykle interesujące, że każdy z mieszkańców chciałby je obejrzeć w swoim domu, leżąc na kanapie i wcinając staszicchipsy. I tu pojawia się problem. Mieszkańcy nie grzeszą pracowitością, co w następstwie skutkuje biedą - w całej krainie jest tylko jedna antena satelitarna! Nie po to jednak mają IQ, żeby się poddawać. Postanowili zakupić kable w pobliskiej hurtowni i w taki sposób połączyć nimi domy, aby każdy miał dostęp do transmisji (co tam kogo prawa autorskie obchodzą...). W hurtowni można zamówić dowolną liczbę kabli jednakowej, całkowitej długości. Nieszczęsna konstrukcja kabla sprawia, że można go używać tylko w całości (bez przecinania) i łączyć nim bezpośrednio dwa domy (o ile długość kabla na to pozwala - jeśli kabel jest za długi, można go jednak odpowiednio zwinąć). Jak to w świecie – nic za darmo, jeden kabel długości k kosztuje k staszictalarów.
Po wpadnięciu na pomysł połączenia domów kablami, tak, aby każdy miał dostęp do anteny, mieszkańcy, w poczuciu dumy z dobrzej wykonanej pracy intelektualnej, poszli się zabawić. Dopiero następnego dnia, uświadomili sobie, że muszą zamówić odpowiedniej długości kable. Chcieliby jednak wydać jak najmniej. W tym celu poprosili Ciebie o obliczenie minimalnych kosztów związanych z realizacją planu. Mieszkańcy uzgodnili także, że wspólna antena może stać na dachu dowolnego z domów, a jej lokalizację zostawili Tobie do wyboru.
W pierwszym wierszu znajduje się jedna liczba całkowita n (1 <= n <= 5000) oznaczająca liczbę domów. W następnych n wierszach znajdują się współrzędne domów. Wiersz i + 1 zawiera dwie liczby całkowite x oraz y (-300000 <= x, y <= 300000) będące współrzędnymi i-tego domu.
W testach wartych 30% punktów zachodzi 1 <= n <= 100 oraz 0 <= x, y <= 1000.
W testach wartych 80% punktów zachodzi 1 <= n <= 1000.
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczająca minimalny koszt połączenia wszystkich domów tak, aby każdy mieszkaniec mógł obejrzeć mistrzostwa.
Wejście 6 -1 1 -1 -1 1 -1 1 1 2 2 3 3 Wyjście 10
Umieszczamy antenę w domu nr 6. Zamawiamy 5 kabli o długości 2. Łączymy kolejno domy 6 i 5, 5 i 4, 4 i 3, 3 i 2, 2 i 1. Kabli jest 5, każdy kosztował 2 staszictalary: 2 * 5 = 10.
[Zgłoś rozwiązanie] [Moje zgłoszenia]