Problem description
Dany jest wielokąt wypukły o N wierzchołkach, które są podane w kolejności przeciwnej do ruchu wskazówek zegara. Twoim zadaniem jest napisać program, które na każde z Q zapytań odpowie, czy dany punkt należy do wielokąta (znajduje się wewnątrz niego, na jednej z jego krawędzi lub pokrywa się z jednym z jego wierzchołków).
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę wierzchołków wielokąta. Następnie znajduje się N wierszy, i-ty z nich zawiera dwie liczby całkowite oddzielone pojedynczym odstępem: xi oraz yi - współrzędne i-tego wierzchołka wielokąta.
Kolejny wiersz zawiera jedną liczbę całkowitą Q, oznaczającą liczbę zapytań. Następnie znajduje się N wierszy, j-ty z nich zawiera dwie liczby całkowite oddzielone pojedynczym odstępem: xj oraz yj - współrzędne punktu w j-tym zapytaniu.
Wyjście
Twój program powinien wypisać Q wierszy. W j-tym wierszu ma wypisać
TAK, gdy punkt z j-tego zapytania należy do wielokąta
lub NIE w przeciwnym przypadku.
Ograniczenia
3 ≤ N, Q ≤ 100 000, − 108 ≤ xi, yi, xj, yj ≤ 108
Przykład
| Input | Output | |
|
|