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.
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.
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).
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).