P9996 [Ynoi2000] hpi

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$.

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$.

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

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