Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-扫描游戏
题目 2669:

蓝桥杯2022年第十三届省赛真题-扫描游戏

时间限制: 2s 内存限制: 320MB 提交: 1116 解决: 134

题目描述

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

如果将物件按照消失的时间排序,则每个物件有一个排名,同时消失的物件排名相同,请输出每个物件的排名,如果物件永远不会消失则输出 −1。 

输入格式

输入第一行包含两个整数 n、L,用一个空格分隔,分别表示物件数量和棒的初始长度。

接下来 n 行每行包含第三个整数 xi , yi ,zi

输出格式

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

样例输入

5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2

样例输出

1 1 3 4 -1

提示

对于 30% 的评测用例,1 ≤ n ≤ 500 ;

对于 60% 的评测用例,1 ≤ n ≤ 5000 ;

对于所有评测用例,1 ≤ n ≤ 200000,−109 ≤ xi , yi ≤ 109,1 ≤ L,zi ≤ 109 。 

标签