APCS202206 第3題雷射測試

zerojudge:https://zerojudge.tw/ShowProblem?problemid=i401

出處：APCS

輸出說明

輸出雷射光共反射幾次。

輸入範例

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

4

2 1 0

5 -3 1

4 2 1

6 -2 0

輸出範例

9

0

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

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

解題策略

模擬，使用adjacency list紀錄相同x可以到達的y到X[]，接著由小到大排序X[]內的y，使用adjacency list紀錄相同y可以到達的x到Y[]，接著由小到大排序Y[]內的x。使用二分搜尋加快速度，本範例二分搜尋可以使用upper_bound找出大於x的第一個元素，lower_bound找出大於等於x的第一個元素。

從(0,0)向東出發找到第一個y=0，x>0的第一個鏡子，使用upper_bound找出x大於的第一個元素。若該鏡子為\，則往南，否則往北。若往南，表示在相同x，使用lower_bound找到第一個y大於等於0的點，該元素指標減1(找到小於0的第一個元素)，表示找到y小於0的第一個鏡子為反射鏡子。若該鏡子為\，則往東，否則往西。依次類推找出所有反射鏡子的個數。