[蓝桥杯 2022 省 A] 扫描游戏

Luogu
IDLGP8777
Time1000ms
Memory512MB
DifficultyP5
模拟计算几何2022排序蓝桥杯省赛
有一根围绕原点 $O$ 顺时针旋转的棒 $OA$,初始时指向正上方(Y 轴正向)。平面中有若干物件,第 $i$ 个物件的坐标为 $\left(x_{i}, y_{i}\right)$,价值为 $z_{i}$。当棒扫到某个物件时,棒的长度会瞬间增长 $z_{i}$,且物件瞬间消失(棒的顶端恰好碰到物件也视为扫到),如果此时增长完的棒又额外碰到了其他物件,也按上述方式消去(它和上述那个点视为同时消失)。 如果将物件按照消失的时间排序,则每个物件有一个排名,同时消失的物件排名相同,请输出每个物件的排名,如果物件永远不会消失则输出 $-1$。 ## Input 输入第一行包含两个整数 $n$、$L$,用一个空格分隔,分别表示物件数量和棒的初始长度。 接下来 $n$ 行每行包含第三个整数 $x_{i}, y_{i}, z_{i}$。 注意存在 $(x_{i}, y_{i})=(0,0)$ 的情况,这些点视为一开始就立刻被碰到。 ## Output 输出一行包含 $n$ 整数,相邻两个整数间用一个空格分隔,依次表示每个物件的排名。 [samples] ## Note 对于 $30 \%$ 的评测用例,$1 \leq n \leq 500$ ; 对于 $60 \%$ 的评测用例,$1 \leq n \leq 5000$; 对于所有评测用例,$1 \leq n \leq 2\times10^5,-10^{9} \leq x_{i}, y_{i} \leq 10^{9}, 1 \leq L, z_{i} \leq 10^{9}$ 。 样蓝桥杯 2022 省赛 A 组 H 题。
Samples
Input #1
5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2
Output #1
1 1 3 4 -1
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2022 省 A] 扫描游戏",
    "description": {
      "content": "有一根围绕原点 $O$ 顺时针旋转的棒 $OA$,初始时指向正上方(Y 轴正向)。平面中有若干物件,第 $i$ 个物件的坐标为 $\\left(x_{i}, y_{i}\\right)$,价值为 $z_{i}$。当棒扫到某个物件时,棒的长度会瞬间增长 $z_{i}$,且物件瞬间消失(棒的顶端恰好碰到物件也视为扫到),如果此时增长完的棒又额外碰到了其他物件,也按上述方式消去(它和上述那个点视为同时消失)",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8777"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一根围绕原点 $O$ 顺时针旋转的棒 $OA$,初始时指向正上方(Y 轴正向)。平面中有若干物件,第 $i$ 个物件的坐标为 $\\left(x_{i}, y_{i}\\right)$,价值为 $z_{i}$。当棒扫到某个物件时,棒的长度会瞬间增长 $z_{i}$,且物件瞬间消失(棒的顶端恰好碰到物件也视为扫到),如果此时增长完的棒又额外碰到了其他物件,也按上述方式消去(它和上述那个点视为同时消失)...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments