Gołębie pocztowe
Limit pamięci: 32 MB
W ramach oszczędności Bajtocki Urząd Pocztowy postanowił odejść od tradycyjnej metody doręczania przesyłek i zatrudnić gołębie do roznoszenia poczty.
W pierwszej kolejności program cięć objął Bajtogród.
W mieście jest ulic biegnących z północy na południe oraz ulic ze wschodu na zachód, tak jak w każdym zadaniu tego typu skrzyżowania utożsamiamy z punktami o obu współrzędnych całkowitych.
Gołąb przelatuje pomiędzy parą sąsiednich skrzyżowań w ciągu jednej minuty.
Wieżowce w mieście są wyjątkowo wysokie, dlatego gołębie mogą latać jedynie nad ulicami.
Magazyn przesyłek znajduje się w punkcie .
Ponieważ gołębie nie radzą sobie z tłumaczeniem przyczyn w opóźnieniu doręczenia, przesyłki należy doręczać jak najszybciej.
Paczka do klienta w punkcie musi być dostarczona dokładnie w minut.
Gołębie potrafią zrzucać paczki w trakcie przelotu i trafiać dokładnie do skrzynki adresata, więc w trakcie drogi do pewnego miejsca mogą one zrzucać paczki do skrzynek na skrzyżowaniach, nad którymi przelatują.
Nie wolno im jednak nadkładać drogi, by to zrobić.
Oblicz ile co najmniej gołębi potrzeba do dostarczenia paczek do wszystkich adresatów.
Wejście
Pierwszy wiersz standardowego wejścia zawiera liczbę całkowitą () oznaczającą liczbę adresatów.
W drugim wierszu podane są współrzędne magazynu, zaś kolejne wierszy zawiera współrzędne poszczególnych adresatów.
Wszystkie współrzędne to pary liczb całkowitych i (.
Dodatkowo każde dwa punkty różnią się na obydwu współrzędnych (tj. wszystkie odcięte i rzędne są różne).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą - minimalną liczbę gołębi, które są potrzebne do dostarczenia przesyłek do wszystkich adresatów.
Przykład
Dla danych wejściowych:
4
0 3
1 2
2 5
3 0
4 1
poprawną odpowiedzią jest:
3
Autor zadania: Jakub Łącki (zapożyczenie z CPSPC 2006).