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.
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.
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 .
W pierwszym i jedynym wierszu standardowego wyjścia powinna zostać wypisana jedna liczba całkowita - minimalna liczba potrzebnych satelitów.
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
Wystarczą satelity w oraz .
Autor zadania: Bartosz Górski (zapożyczenie).