11114. Ідентифікація точок в багатокутниках


Відправити розв'язок

Бали: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C++, Java, Pascal, Python

На координатній площині задано \(N\) багатокутників зі сторонами паралельними осям координат. Багатокутникі не мають самоперетинів.
Знайдіть відповідь на \(Q\) запитів:
-Всередині скількох з цих багатокутників знаходиться точка з координатами \((X+0.5, Y+0,5)\)

Формат вхідних даних

В першому рядку ціле число \(N\) (\(1 \le N \le 10^5\))
В наступних рядках йде опис багатокутників (кожен багатокутних описується двома рядками)
В першому рядку міститься число \(M\) - кількість вершин багатокутника (\(4 \le M \le 10^5\))
В наступному рядку \(M\) пар цілих чисел \(Xi,Yi\) - координати багатокутника в порядку обходу. (\(0 \le Xi,Yi \le 10^5\))

Після опису всіх багатокутників, йде рядок з цілим числом \(Q\) - кількість запитів (\(1 \le Q \le 10^5\))\(1 \le Q \le 10^5\))
В кожному з наступних \(Q\) рядків міститься по два цілих числа \(X,Y\) - координати відповідного запиту (\(0 \le X,Y \le 10^5\))

Формат вихідних даних

Для кожного запиту виведіть відповідь в окремому рядку

Приклад вхідних даних-1

3
4
1 2 1 4 3 4 3 2
4
2 5 2 3 5 3 5 5
4
5 6 5 5 3 5 3 6
3
1 4
2 3
4 5

Приклад вихідних даних-1

0
2
1

Приклад вхідних даних-2

2
4
12 3 12 5 0 5 0 3
12
1 1 1 9 10 9 10 0 4 0 4 6 6 6 6 2 8 2 8 7 2 7 2 1
4
2 6
4 4
6 3
1 8

Приклад вихідних даних-2

0
2
1
1


Коментарі

Ще немає коментарів.