i401. 3. 雷射測試 - 高中生程式解題系統

內容

一個雷射光從 (0,0) 向右邊發射，平面上有很多個鏡子，問雷射光會反射幾次，保證輸入沒有無限循環的情形。

鏡子用三個數字表示 $(x_{i}, y_{i}, t_{i})$ ，代表座標在 $(x_{i}, y_{i})$ 上。 $t_{i} = 0$ 代表示這種 / 擺放方式的鏡子， $t_{i} = 1$ 代表這種 \ 擺放方式的鏡子，保證不會有一個位置有多個鏡子。

輸入說明

輸入一個正整數 $n (1 \leq n \leq 250000)$ ，代表鏡子的數量，接下來有 $n$ 行，第 $i$ 行有三個數字 $x_{i}$ , $y_{i}$ 和 $t_{i}$ 。

子題配分

(20%): $1 \leq n \leq 1000$ , $1 \leq x_{i} \leq 100, | y_{i} | \leq 100$
(80%): $1 \leq n \leq 250000$ , $1 \leq x_{i} \leq 30000, | y_{i} | \leq 30000$

輸出說明

輸出雷射光共反射幾次。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1M
公開測資點#2 (5%): 2.0s , <1M
公開測資點#3 (5%): 2.0s , <1M
公開測資點#4 (5%): 2.0s , <1M
公開測資點#5 (5%): 2.0s , <1M
公開測資點#6 (5%): 2.0s , <1M
公開測資點#7 (5%): 2.0s , <1M
公開測資點#8 (5%): 2.0s , <10M
公開測資點#9 (5%): 2.0s , <10M
公開測資點#10 (5%): 2.0s , <10M
公開測資點#11 (5%): 2.0s , <10M
公開測資點#12 (5%): 2.0s , <10M
公開測資點#13 (5%): 2.0s , <10M
公開測資點#14 (5%): 2.0s , <10M
公開測資點#15 (5%): 2.0s , <10M
公開測資點#16 (5%): 2.0s , <10M
公開測資點#17 (5%): 2.0s , <10M
公開測資點#18 (5%): 2.0s , <1M
公開測資點#19 (5%): 2.0s , <10M

提示：

本題若使用遞迴實作，可能因為遞迴深度過深而造成執行時期錯誤。

範例測資一，見題目敘述內的圖表。

範例測資二可以發現沒有任何 $y = 0$ 的鏡子，因此反射次數為 $0$ 。

標籤:

APCS bfs vector 二分搜尋圖論模擬

出處:

2022年6月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
42003	a127000555 (OAO)	i401	喜歡指標的你但討厭二分搜的你，歡迎參考	225	2024-09-18 02:11
45509	zhoudaniel02 ... (周孝倫)	i401	作法提示	36	2025-03-11 15:03
45010	ray200695071 ... (Ray Liu)	i401	C++ 二分搜	119	2025-01-02 04:17
41196	guovinn@gmai ... (你爹)	i401	C++解法	296	2024-07-10 18:58
41171	glps1004@gma ... (Ian)	i401		165	2024-07-08 19:27