P2028 - [蓝桥杯2022初赛] 扫描游戏

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：315 通过：41

有一根围绕原点O 顺时针旋转的棒OA，初始时指向正上方（Y 轴正向）。
在平面中有若干物件，第i 个物件的坐标为(xi, yi) ，价值为zi。
当棒扫到某个物件时，棒的长度会瞬间增长zi，且物件瞬间消失（棒的顶端恰好碰到物件也视为扫到）。
如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去（它和上述那个点视为同时消失）。
如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同。
请输出每个物件的排名，如果物件永远不会消失则输出-1。

输入第一行包含两个整数n、L，用一个空格分隔，分别表示物件数量和棒的初始长度。
接下来n 行每行包含第三个整数xi, yi, zi。
30%的测试数据：1≤n≤500；
60%的测试数据：1≤n≤5000；
100%的测试数据：1≤n≤200000，-10^9 ≤xi,yi≤10^9，1≤L,zi≤10^9。

输出一行包含n个整数，相邻两个整数间用一个空格分隔，依次表示每个物件的排名。

1 1 3 4 -1

挑战题计算几何线段树

2028: [蓝桥杯2022初赛] 扫描游戏

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签