8487번 - Satelity 다국어

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 x:

Satelity szpiegowskie można umieszczać tylko na prostej y = H. 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.

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite n i H (1 ≤ n ≤ 100 000, 1 ≤ H ≤ 1 000 000) oddzielone pojedynczymi odstępami. Każdy z następnych n wierszy zawiera opis krajobrazu Bajtlandii. W każdym z nich znajdują się trzy liczby całkowite x_i, y_i i z_i (0 ≤ x_i ≤ 1 000 000, 0 ≤ y_i < H, z_i ∈ {0, 1}) oddzielone pojedynczym odstępem; (x_i, y_i) określa współrzędne punktu, a z_i = 1 oznacza, że mogą w nim mieć swoją siedzibę buntownicy, a z_i = 0 w przeciwnym wypadku. Możesz założyć, że y₁ oraz y_n będą zawsze równe 0, a punkty będą podawane w kolejności ściśle rosnącej współrzędnej x.

W pierwszym i jedynym wierszu standardowego wyjścia powinna zostać wypisana jedna liczba całkowita - minimalna liczba potrzebnych satelitów.

Wystarczą satelity w x = 31.(6) oraz x = 112.