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.
Prezydent Bajtogrodu planuje budowę sieci komunikacyjnej, składającej się z przystanków i linii autobusowych. Dwa spośród przystanków, i zostaną wybrane na węzły przesiadkowe, a pozostałe przystanków zostanie połączonych bezpośrednimi liniami autobusowymi z albo (ale nie z obydwoma jednocześnie). Ponadto, w mieście zostanie utworzona linia autobusowa łącząca obydwa węzły przesiadkowe. Z powodu braku funduszy, nie powstaną żadne inne połączenia autobusowe.
Odległość pomiędzy przystankami autobusowymi połączonymi bezpośrednią linią autobusową, znajdującymi się w punktach o współrzędnych i wynosi . Jeżli dwa przystanki połączone są bezpośrednio z tym samym węzłem, to odległość między nimi jest sumą odległości obydwóch przystanków od tego węzła. Jeśli dwa przystanki połączone są z różnymi węzłami przesiadkowymi, to odległość między nimi jest sumą odległości każdego z przystanków od węzła do którego jest on podłączony i odległości pomiędzy węzłami przesiadkowymi.
Napisz program, który:
W pierwszej lini standardowego wejścia znajudje się jedna liczba całkowita (), oznaczająca liczbę wszystkich przystanków w mieście. Każda z kolejnych linii zawiera dwie liczby całkowite dodatnie, nie większe niż - są to współrzędne jednego z przystanków autobusowych. W danym punkcie może znajdować się co najwyżej jeden przystanek.
Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia wypisać jedną liczbę całkowitą - największą odległość pomiędzy dwoma przystankami autobusowymi w mieście, przy optymalnym doborze węzłów przesiadkowych i połączeniu przystanków z węzłami.
Dla danych wejściowych:
6 1 7 16 6 12 4 4 4 1 1 11 1
poprawną odpowiedzią jest:
20
Przykładowym danym wejściowym odpowiada powyższy schemat. Przystanki numer 3 i 4 zostały wybrane na węzły przesiadkowe.
Zapożyczone ze starego IOI przez Jakuba Łąckiego.