eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Есть N точек на плоскости. Точки равномерно распределены внутри квадрата [0..C]×[0..C].

Вам нужно научиться отвечать на запрос "сколько точек лежит в полуплоскости"?

Giriş verilənləri

Число точек N (1N5·10^4), число запросов M (1M5·10^4), константа C (целое число от 1 до 10^4). Далее Nточек (X, Y) с целочисленными координатами. Далее M полуплоскостей (a, b, c). Числа a, b, c — целые, по модулю не превосходят 10^4. a^{2 }+ b^{2 }0. Считается, что точка лежит в полуплоскости тогда и только тогда, когдаax + by + c 0.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3 4 10
5 5
1 7
7 4
1 1 -9
1 1 -10
1 1 -11
1 1 -12
Çıxış verilənləri #1
2
2
1
0