Głupie elfy znów zaatakowały Twoje królestwo, lordzie Gleboryju, Władco Połowy Krasnoludów! Trzeba odeprzeć ich atak. Niestety, jest ich strasznie dużo - ponamnażały się w tych lasach od czasu ostatniej bitwy. Aby ich pokonać, musisz zawezwać na pomoc swojego brata Wszobrodego, Władcę Drugiej Połowy Krasnoludów.
Dawno temu z bratem wymyśliliście system informowania się o atakach głupich elfów. Pomiędzy waszymi miastami, żyje na powierzchni wiele rodzin krasnoludzkich, każda z nich posiada Wielką Metalową Antenę. Wielka Metalowa Antena potrafi odbierać sygnał i wysyłać go dalej, ale tylko pod kątem czterdziestu pięciu stopni do osi układu współrzędnych (ale na wszystkie cztery, tak zdefiniowane, strony). W ten sposób, być może za pomocą wielu Wielkich Metalowych Anten jako stacji pośrednich, uda się przekazać sygnał pomocy do miasta Wszobrodego. Zarówno Twoje miasto, jak i miasto Wszobrodego, również posiada Wielką Metalową Antenę.
Jednak głupie elfy przejrzały wasz system komunikacji i rzuciły na ziemię wiele czarów Kula Ciemności, każdy z nich pogrąża w ciemności (która nie przepuszcza sygnałów Wielkiej Metalowej Anteny) pewien obszar na ziemi. Głupie elfy są głupie i każda ich kula ciemności, jak sama nazwa wskazuje, pogrąża w ciemności kwadrat o bokach równoległych do osi układu współrzędnych.
Musisz więc napisać szybko program, który sprawdzi, czy jesteś, mimo kul ciemności, w stanie przekazać bratu wiadomość o ataku. Jeśli się da, to chcesz wiedzieć, ile minimalnie Wielkich Metalowych Anten (wliczając w to Twoją antenę i antenę z miasta Wszobrodego) musi być zaangażowanych w informowanie.
W dodatku możesz założyć, że:
W pierwszej linii wejścia są dwie liczby 2 <= n < = 100 000 i 0 <= m <= 100 000, oznaczające liczbę Wielkich Metalowych Anten oraz liczbę rzuconych czarów Kula Ciemności. Pierwsza antena to antena w Twoim mieście, ostatnia antena to antena w mieście Wszobrodego. Następnie jest n linijek, w każdej są dwie liczby całkowite -1 000 000 000 <= x,y <= 1 000 000 000, oznaczające współrzędne Wielkich Metalowych Anten. Następne m linijek definiuje rzucone czary Kula Ciemności: w każdej linii są trzy liczby całkowite -1 000 000 000 <= x,y <= 1 000 000 000, 1 <= d <= 1 000 000 000, oznaczające, że Kula Ciemności zaciemnia obszar będący kwadratem o środku w (x,y) i boku 2d. Możesz założyć, że wartości bezwzględne współrzędnych rogów kwadratu zaciemnonego są niewiększe niż 1 000 000 000.
W pierwszej i jedynej linii wyjścia wypisz NIE, jeśli nie można poinformować Wszobrodego, lub liczbę dodatnią całkowitą, oznaczającą, ile minimalnie Wielkich Metalowych Anten musisz zaangażować w informowanie (wliczając w to anteny 1 i n).
Dla danych
5 2 -4 0 0 -4 4 0 0 4 -4 8 -2 2 1 -3 3 1
prawidłową odpowiedzią jest:
5
A dla danych:
4 2 -4 0 0 -4 4 0 0 4 -2 2 1 2 -2 1
prawidłową odpowiedzią jest:
NIE
[Zgłoś rozwiązanie] [Moje zgłoszenia]