有一根圍繞原點(diǎn) O 順時(shí)針旋轉(zhuǎn)的棒 OA,初始時(shí)指向正上方(Y 軸正向)。 在平面中有若干物件,第 i 個(gè)物件的坐標(biāo)為 (xi , yi) ,價(jià)值為 zi。當(dāng)棒掃到某個(gè)物件時(shí),棒的長(zhǎng)度會(huì)瞬間增長(zhǎng) zi,且物件瞬間消失(棒的頂端恰好碰到物件也視為掃到),如果此時(shí)增長(zhǎng)完的棒又額外碰到了其他物件,也按上述方式消去 (它和上述那個(gè)點(diǎn)視為同時(shí)消失)。
如果將物件按照消失的時(shí)間排序,則每個(gè)物件有一個(gè)排名,同時(shí)消失的物件排名相同,請(qǐng)輸出每個(gè)物件的排名,如果物件永遠(yuǎn)不會(huì)消失則輸出 ?1。
輸入第一行包含兩個(gè)整數(shù) n、L,用一個(gè)空格分隔,分別表示物件數(shù)量和棒的初始長(zhǎng)度。
接下來(lái) n 行每行包含第三個(gè)整數(shù) xi , yi ,zi。
5 2 0 1 1 0 3 2 4 3 5 6 8 1 -51 -33 2
1 1 3 4 -1
對(duì)于 30% 的評(píng)測(cè)用例,1 ≤ n ≤ 500 ;
對(duì)于 60% 的評(píng)測(cè)用例,1 ≤ n ≤ 5000 ;
對(duì)于所有評(píng)測(cè)用例,1 ≤ n ≤ 200000,?109 ≤ xi , yi ≤ 109,1 ≤ L,zi ≤ 109 。
第十三屆藍(lán)橋杯大賽軟件賽省賽 C/C++ 大學(xué) A 組 |
|
---|---|
C題 | |
D題 | |
E題 | |
F題 | |
G題 | |
H題 | |
I題 | |
J題 |
注意事項(xiàng):
1. 對(duì)于編程題目,要求選手給出的解答完全符合 GNU C/C++ 標(biāo)準(zhǔn),不能使用諸如繪圖、Win32API、中斷調(diào)用、硬件操作或與操作系統(tǒng)相關(guān)的 API。
2. 代碼中允許使用 STL 類庫(kù)。
3. main 函數(shù)結(jié)束必須返回 0。
4. 所有依賴的函數(shù)必須明確地在源文件中 #include
5. 提交時(shí),注意選擇使用C或C++語(yǔ)言。
比賽結(jié)束,可以到題集中訓(xùn)練,長(zhǎng)期有效,2022年第十三屆藍(lán)橋杯大賽軟件類省賽C/C++大學(xué)A組真題