Satelity
Limit pamięci: 64 MB
Bajtlandia przeżywa kolejny kryzys.
Władzę przejęło wojsko.
Aby zakończyć wojnę domową, dowódcy muszą już tylko znaleźć i wyeliminować
pozostałości tych, którym nie spodobał się nowy układ sił.
Nie jest to jednak takie proste...
Dzięki (mniej lub bardziej dobrowolnym) raportom informatorów udało się ustalić
listę potencjalnych miejsc, w których może znajdować się baza buntowników.
Jako, że długotrwałe poszukiwania prowadzone w tych punktach nie przyniosły
żadnych rezultatów, postanowiono podejść do problemu trochę inaczej - poczekać,
aż przeciwnicy sami się ujawnią.
Aby przedwcześnie nie wzbudzić ich podejrzeń, obserwacja będzie prowadzona za
pomocą sieci satelitów szpiegowskich.
Bajtlandię można sobie wyobrażać jako dwuwymiarowy krajobraz powstały przez
połączenie punktów o różnych współrzędnych :
Satelity szpiegowskie można umieszczać tylko na prostej .
Każdy taki satelita obserwuje te punkty, z którymi można go połączyć za
pomocą odcinka, który nie przecina krzywej opisującej krajobraz (dotykania
nie traktujemy jako przecinania).
Twoim zadaniem jest obliczenie minimalnej liczby takich satelitów
wystarczającej do jednoczesnej obserwacji wszystkich miejsc, w których
podejrzewa się istnienie bazy rebeliantów.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby
całkowite i (, )
oddzielone pojedynczymi odstępami.
Każdy z następnych wierszy zawiera opis krajobrazu Bajtlandii.
W każdym z nich znajdują się trzy liczby całkowite , i
(, , )
oddzielone pojedynczym odstępem; (, ) określa współrzędne
punktu, a oznacza, że mogą w nim mieć swoją siedzibę
buntownicy, a w przeciwnym wypadku.
Możesz założyć, że oraz będą zawsze równe 0, a punkty będą
podawane w kolejności ściśle rosnącej współrzędnej .
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna zostać
wypisana jedna liczba całkowita - minimalna liczba potrzebnych
satelitów.
Przykład
Dla danych wejściowych:
9 30
0 0 1
15 5 1
25 20 1
40 10 1
60 5 1
70 15 1
82 0 1
90 8 1
100 0 1
poprawną odpowiedzią jest:
2
Wyjaśnienie
Wystarczą satelity w oraz .
Autor zadania: Bartosz Górski (zapożyczenie).