P8529 [Ynoi2003] 赫露艾斯塔


给定 $n$ 个互不相同的点 $(x_i,y_i),\;1\le i\le n$，$m$ 个集合 $S_j=\{(x_i,y_i)\mid A_jx_i+B_jy_i+C_j>0\},\;1\le j\le m$。 你需要找出一个 $1,2,\dots,m$ 的排列 $p_1,\dots,p_m$，使得 $|S_{p_1}|+\sum\limits_{i=2}^m |S_{p_i}\oplus S_{p_{i-1}}|\le M$。 $M$ 是给定的常数，$A\oplus B$ 表示 $(A\cup B)-(A\cap B)$。

第一行两个整数 $n,m$； 接下来 $n$ 行每行两个整数表示 $x_i,y_i$； 接下来 $m$ 行每行三个整数表示 $A_j,B_j,C_j$。

输出 $m$ 行，依次表示 $p_1,\dots,p_m$。

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于 $100\%$ 的数据，满足 $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$。 实际上数据是随机生成的。