{"problem":{"name":"[Ynoi2003] 赫露艾斯塔","description":{"content":"给定 $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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":20000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8529"},"statements":[{"statement_type":"Markdown","content":"给定 $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$。\n\n你需要找出一个 $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$。\n\n$M$ 是给定的常数，$A\\oplus B$ 表示 $(A\\cup B)-(A\\cap B)$。\n\n## Input\n\n第一行两个整数 $n,m$；\n\n接下来 $n$ 行每行两个整数表示 $x_i,y_i$；\n\n接下来 $m$ 行每行三个整数表示 $A_j,B_j,C_j$。\n\n## Output\n\n输出 $m$ 行，依次表示 $p_1,\\dots,p_m$。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/1kgx165m.png)\n\n## Note\n\nIdea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078\n\n对于 $100\\%$ 的数据，满足\n\n$1\\le n\\le 10^5$\n\n$1\\le m\\le 2\\times 10^5$\n\n$M=1.8\\times 10^8$\n\n$A_j^2+B_j^2>0$\n\n$-10^8\\le x_i,y_i,A_j,B_j,C_j\\le 10^8$。\n\n实际上数据是随机生成的。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8529","tags":["2003","Special Judge","O2优化","Ynoi"],"sample_group":[["5 3\n2021 700\n-9384 1031\n2201 2561\n4982 6255\n-1700 388\n-2151 1808 -4359815\n-2850 -1980 7147359\n-924 217 -8902828","2\n1\n3"]],"created_at":"2026-03-03 11:09:25"}}