Na tym laboratorium kontynuujemy prezentację zastosowań biblioteki STL do implementacji efektywnych algorytmów, tak się akurat składa, że nadal grafowych. Tym razem na tapecie algorytm Dijkstry.
Zadanie KAP (Kapitan)
Dostępna pamięć: 256MB.
Kapitan Bajtazar przemierza wody Morza Bajtockiego wraz ze swoim niezastąpionym pierwszym oficerem Bajtkiem. Na morzu znajduje się \( \displaystyle n \) wysp, które numerujemy liczbami od 1 do \( \displaystyle n \). Przy wyspie numer 1 przycumował statek kapitana. W ramach wyprawy kapitan planuje popłynąć na wyspę numer \( \displaystyle n \).
W trakcie rejsu statek zawsze porusza się w jednym z czterech kierunków świata: na północ, południe, wschód lub zachód. W każdym momencie przy sterach stoi albo kapitan, albo pierwszy oficer. Za każdym razem, gdy statek wykona skręt o \( \displaystyle 90^\circ \), zmieniają się oni przy sterach.
Po drodze statek może zatrzymywać się przy innych wyspach. Po każdym postoju kapitan może zdecydować, czy obejmuje stery jako pierwszy. Innymi słowy, na każdym fragmencie trasy prowadzącym z wyspy do wyspy jeden z marynarzy obejmuje stery, gdy statek płynie na północ lub południe, a drugi z nich steruje podczas rejsu na wschód lub zachód. W szczególności, jeśli pewien fragment trasy prowadzi dokładnie w jednym z czterech kierunków świata, na tym fragmencie steruje tylko jeden z marynarzy.
Kapitan zastanawia się teraz, jak zaplanować trasę najbliższego rejsu i podział pracy, by spędzić jak najmniej czasu przy sterze. Jednocześnie kapitan nie przejmuje się, jak długa będzie wyznaczona trasa. Przyjmujemy, że statek płynie ze stałą prędkością jednej jednostki na godzinę.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą \( \displaystyle n \) ( \( \displaystyle 2 \le n \le 200\,000 \) ) oznaczającą liczbę wysp na morzu. Dla uproszczenia na Morze Bajtockie nanosimy układ współrzędnych, którego osie są równoległe do kierunków świata. Każdą z wysp reprezentujemy jako pojedynczy punkt. Kolejne \( \displaystyle n \) wierszy zawiera opisy wysp: \( \displaystyle i \)-ty z nich zawiera dwie liczby całkowite \( \displaystyle x_i \), \( \displaystyle y_i \) ( \( \displaystyle 0 \le x_i,y_i \le 1\,000\,000\,000 \) ) oznaczające współrzędne \( \displaystyle i \)-tej wyspy na morzu. Każda wyspa ma inne współrzędne.
Wyjście
Twój program powinien wypisać na wyjście jedną liczbę całkowitą, oznaczającą najmniejszą liczbę godzin, przez które kapitan będzie musiał sterować statkiem na trasie z wyspy numer 1 do wyspy numer \( \displaystyle n \).
Przykład
Dla danych wejściowych:
5
2 2
1 1
4 5
7 1
6 7
poprawnym wynikiem jest:
2
Wyjaśnienie do przykładu: Kapitan może wyznaczyć trasę, którą zaznaczono na obrazku. W trakcie rejsu z wyspy 1 (współrzędne (2, 2)) na wyspę 4 (współrzędne (7, 1)) kapitan steruje tylko przez godzinę, gdy statek płynie na południe. W trakcie drugiego fragmentu podróży kapitan steruje jedynie wtedy, gdy statek porusza się na wschód.
