[Ynoi2003] 赫露艾斯塔

Luogu

IDLGP8529

Time20000ms

Memory512MB

DifficultyP7

2003Special JudgeO2优化Ynoi

给定 $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)$。 ## Input 第一行两个整数 $n,m$；接下来 $n$ 行每行两个整数表示 $x_i,y_i$；接下来 $m$ 行每行三个整数表示 $A_j,B_j,C_j$。 ## Output 输出 $m$ 行，依次表示 $p_1,\dots,p_m$。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/1kgx165m.png) ## Note 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$。实际上数据是随机生成的。

Samples

Input #1

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

Output #1

2
1
3

API Response (JSON)

{
  "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments