EduBrick

H. Точки в прямоугольнике

4000 мс · 256 МБ · всё или ничего

Дан набор точек на плоскости и запросы «сколько точек лежит внутри прямоугольника». Стороны прямоугольника считаются принадлежащими ему.

Первая задача занятия, где в дереве вообще нет исходного массива.

Формат ввода

В первой строке NN (0≤N≤1050 \le N \le 10^5) — количество точек. В следующих NN строках — координаты точек xix_i, yiy_i (∣xi∣,∣yi∣≤109|x_i|, |y_i| \le 10^9). Далее MM (0≤M≤1050 \le M \le 10^5) — количество запросов, и MM строк с числами x1x_1, y1y_1, x2x_2, y2y_2 — левый нижний и правый верхний углы прямоугольника (x1≤x2x_1 \le x_2, y1≤y2y_1 \le y_2).

Формат вывода

Для каждого запроса выведите количество точек внутри прямоугольника на отдельной строке.

Примеры

ввод
5
-1 -1
-1 0
0 1
0 -1
1 -1
5
0 -3 3 1
-1 -1 1 1
3 4 5 6
-1 -1 -1 -1
0 0 0 5
вывод
3
5
0
1
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.