小明最近迷上了一款名為《掃雷》的游戲。其中有一個關(guān)卡的任務(wù)如下, 在一個二維平面上放置著 n 個炸雷,第 i 個炸雷 (xi , yi ,ri) 表示在坐標(biāo) (xi , yi) 處存在一個炸雷,它的爆炸范圍是以半徑為 ri 的一個圓。
為了順利通過這片土地,需要玩家進行排雷。玩家可以發(fā)射 m 個排雷火箭,小明已經(jīng)規(guī)劃好了每個排雷火箭的發(fā)射方向,第 j 個排雷火箭 (xj , yj ,rj) 表示這個排雷火箭將會在 (xj , yj) 處爆炸,它的爆炸范圍是以半徑為 rj 的一個圓,在其爆炸范圍內(nèi)的炸雷會被引爆。同時,當(dāng)炸雷被引爆時,在其爆炸范圍內(nèi)的炸雷也會被引爆?,F(xiàn)在小明想知道他這次共引爆了幾顆炸雷?
你可以把炸雷和排雷火箭都視為平面上的一個點。一個點處可以存在多個炸雷和排雷火箭。當(dāng)炸雷位于爆炸范圍的邊界上時也會被引爆。
輸入的第一行包含兩個整數(shù) n、m.
接下來的 n 行,每行三個整數(shù) xi , yi ,ri,表示一個炸雷的信息。
再接下來的 m 行,每行三個整數(shù) xj , yj ,rj,表示一個排雷火箭的信息。
2 1 2 2 4 4 4 2 0 0 5
2
示例圖如下,排雷火箭 1 覆蓋了炸雷 1,所以炸雷 1 被排除;炸雷 1 又覆蓋了炸雷 2,所以炸雷 2 也被排除。
對于 40% 的評測用例:0 ≤ x, y ≤ 109 , 0 ≤ n, m ≤ 103 , 1 ≤ r ≤ 10.
對于 100% 的評測用例:0 ≤ x, y ≤ 109 , 0 ≤ n, m ≤ 5 × 104 , 1 ≤ r ≤ 10.
第十三屆藍(lán)橋杯大賽軟件賽省賽 C/C++ 大學(xué) B 組 | |
---|---|
C題 | |
D題 | |
E題 | |
F題 | |
G題 | |
H題 | |
I題 | |
J題 |
注意事項:
1. 對于編程題目,要求選手給出的解答完全符合 GNU C/C++ 標(biāo)準(zhǔn),不能使用諸如繪圖、Win32API、中斷調(diào)用、硬件操作或與操作系統(tǒng)相關(guān)的 API。
2. 代碼中允許使用 STL 類庫。
3. main 函數(shù)結(jié)束必須返回 0。
4. 所有依賴的函數(shù)必須明確地在源文件中 #include
5. 提交時,注意選擇使用C或C++語言。
本比賽結(jié)束依舊可以提交,請見題集2022年第十三屆藍(lán)橋杯大賽軟件類省賽C/C++大學(xué)B組真題