eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Точки в полуплоскости

Точки в полуплоскости

Есть \textbf{N} точек на плоскости. Точки равномерно распределены внутри квадрата \[\textbf{0}..\textbf{C}\]×\[\textbf{0}..\textbf{C}\]. Вам нужно научиться отвечать на запрос "сколько точек лежит в полуплоскости"? \InputFile Число точек \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{5·10^4}), число запросов \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{5·10^4}), константа \textbf{C} (целое число от \textbf{1} до \textbf{10^4}). Далее \textbf{N} точек (\textbf{X}, \textbf{Y}) с целочисленными координатами. Далее \textbf{M} полуплоскостей (\textbf{a}, \textbf{b}, \textbf{c}). Числа \textbf{a}, \textbf{b}, \textbf{c} --- целые, по модулю не превосходят \textbf{10^4}. \textbf{a^\{2 \}+ b^\{2 \}}≠ \textbf{0}. Считается, что точка лежит в полуплоскости тогда и только тогда, когда \textbf{ax + by + c }≥ \textbf{0}. \OutputFile Для каждого из \textbf{M} запросов одно целое число --- количество точек в полуплоскости.
Ліміт часу 3 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
3 4 10
5 5
1 7
7 4
1 1 -9
1 1 -10
1 1 -11
1 1 -12
Вихідні дані #1
2
2
1
0