Background

Problem Description

Given $n$ distinct points $(x_i,y_i)$, $1\le i\le n$, and $m$ sets $S_j=\{(x_i,y_i)\mid A_jx_i+B_jy_i+C_j>0\}$, $1\le j\le m$.

You need to find a permutation $p_1,\dots,p_m$ of $1,2,\dots,m$ such that

$$|S_{p_1}|+\sum\limits_{i=2}^m |S_{p_i}\oplus S_{p_{i-1}}|\le M.$$

$M$ is a given constant, and $A\oplus B$ means $(A\cup B)-(A\cap B)$.

Input Format

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

The next $n$ lines each contain two integers $x_i,y_i$.

The next $m$ lines each contain three integers $A_j,B_j,C_j$.

Output Format

Output $m$ lines, in order, representing $p_1,\dots,p_m$.

5 3
2021 700
-9384 1031
2201 2561
4982 6255
-1700 388
-2151 1808 -4359815
-2850 -1980 7147359
-924 217 -8902828

2
1
3

Hint

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

Constraints for $100\%$ of the testdata:

$1\le n\le 10^5$.

$1\le m\le 2\times 10^5$.

$M=1.8\times 10^8$.

$A_j^2+B_j^2>0$.

$-10^8\le x_i,y_i,A_j,B_j,C_j\le 10^8$.

In fact, the data is randomly generated.

Translated by ChatGPT 5