a307:
3.雷射測試[202206APCS]
內容
一個雷射光從 (0,0) 向右邊發射，平面上有很多個鏡子，問雷射光會反射幾次，保證輸入沒有無限循環的情形。
鏡子用三個數字表示 (xi,yi,ti)，代表座標在 (xi,yi) 上。ti=0 代表示這種 / 擺放方式的鏡子，ti=1 代表這種 \ 擺放方式的鏡子，保證不會有一個位置有多個鏡子。
輸入說明
輸入一個正整數 n(1≤n≤250000)，代表鏡子的數量，接下來有 n 行，第 i 行有三個數字 xi, yi 和 ti。
子題配分
- (20%): 1≤n≤1000, 1≤xi≤100,|yi|≤100
- (80%): 1≤n≤250000,
輸出說明
輸出雷射光共反射幾次。
範例輸入
#1
10 2 0 1 2 -1 1 7 -1 0 7 2 1 4 2 0 4 1 0 3 1 1 3 2 0 1 -1 1 1 4 0
範例輸出
#1
9
範例輸入
#2
4 2 1 0 5 -3 1 4 2 1 6 -2 0
範例輸出
#2
0
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 ：
-
本題若使用遞迴實作，可能因為遞迴深度過深而造成執行時期錯誤。
範例測資一，見題目敘述內的圖表。範例測資二可以發現沒有任何 y=0 的鏡子，因此反射次數為 0。
標籤: - 用vector <map <int, int> , int> 存鏡子的座標＆鏡子的方向
- 使用二分搜（upper_bound）找到離反射點最近的鏡子座標
- 因為y可能是負數，-30000 <= y <= 30000，所以都加上N(N = 35000)，解決陣列key不能為負數的問題
出處:
2022年6月APCS，演算法海牛
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||