Problem Description

Given $n$ pairwise distinct points $(x_i, y_i)$ and $m$ queries. Each query gives $A, B, C$. You need to count the number of pairs $(i, j)$ that satisfy $x_i < x_j$, $y_i < y_j$, $A x_i + B y_i + C > 0$, and $A x_j + B y_j + C > 0$.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain two integers $x_i, y_i$, for $i = 1, \dots, n$.

The next $m$ lines each contain three integers, representing a query $A, B, C$.

Output Format

For each query, output one line containing one integer, which is the answer to this query.

5 2
2003 -553
-141 1230
-6854 9658
9319 -1777
7773 3306
1113 -3086 -15864589
162 550 -21287

0
1

Hint

Idea: nzhtl1477 & ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Constraints: For $100\%$ of the testdata, $A^2 + B^2 > 0$, $|A|, |B|, |C| \le 10^8$, $1 \le n, m \le 2 \times 10^5$, $|x_i|, |y_i| \le 10^4$. The $x_i, y_i$ are chosen uniformly at random, but it is guaranteed that there are no duplicate points.

For $25\%$ of the testdata, $n, m \le 10^3$.

For another $25\%$ of the testdata, $A = 0$.

For another $25\%$ of the testdata, $C = 0$.

For another $25\%$ of the testdata, there are no special constraints.

Translated by ChatGPT 5