P8529 [Ynoi2003] Heru Aista


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

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 $m$ lines, in order, representing $p_1,\dots,p_m$.

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