P8261 [CTS2022] Socks

Given $n$ points $(x_i, y_i, c_i)$, $i = 1, 2, \dots, n$. There are $m$ queries. Each query gives $A, B, C$, and asks for the number of ordered pairs $(i, j)$ such that $Ax_i + By_i + C < 0$, $Ax_j + By_j + C < 0$, and $c_i = c_j$.

The first line contains two integers $n\ m$. The next $n$ lines each contain three integers $x_i\ y_i\ c_i$, $i = 1, 2, \dots, n$. The next $m$ lines each contain three integers $A\ B\ C$.

Output $m$ lines, each containing one integer, representing the answer.

Sample explanation: The first query corresponds to $(2, 2)(3, 3)$. The second query corresponds to $(1, 1)(2, 2)(2, 4)(3, 3)(3, 5)(4, 2)(4, 4)(5, 3)(5, 5)$. Constraints: For $5\%$ of the testdata, $n, m \le 10^3$. For another $10\%$ of the testdata, $c_i \le 2$. For another $15\%$ of the testdata, $c_i \le 100$. For another $15\%$ of the testdata, $\max(|x_i|, |y_i|) = 10^6$. For another $15\%$ of the testdata, $|A| = |B| = 1$. For another $10\%$ of the testdata, $n \le 20000,\; m \le 200000$. For the remaining testdata, there are no special constraints. Each part of the testdata forms a subtask, with no dependencies. All testdata satisfy: $1 \le n \le 50000$. $1 \le m \le 500000$. $A^2 + B^2 > 0$. $-10^9 \le x_i, y_i, A, B, C \le 10^9$. $1 \le c_i \le n$. All values are integers. When $i \ne j$, $x_i \ne x_j$ or $y_i \ne y_j$. For all testdata except Subtask 4, the $x, y$ coordinates of the $n$ points are independently and uniformly randomly chosen within some preset intervals, and it is guaranteed that there are no duplicate points. For the $i$-th point, $c_i$ and $x_i, y_i$ are independently randomly chosen, but the distribution of $c_i$ has no special restrictions. Translated by ChatGPT 5