EduBrick

Сколько точек в угле

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

Даны nn точек, отличных от начала координат, и qq запросов. Каждый запрос — угол с вершиной в начале координат, заданный двумя точками на сторонах; берётся угол, меньший развёрнутого.

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

Формат ввода

В первой строке nn и qq (1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5). В следующих nn строках координаты точек (∣x∣,∣y∣≤106|x|, |y| \le 10^6, точка не совпадает с началом координат). В следующих qq строках по четыре числа x1x_1, y1y_1, x2x_2, y2y_2 — точки на сторонах очередного угла; векторное произведение соответствующих векторов не равно нулю.

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

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

Примеры

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