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的第一個鏡子為反射鏡子。若該鏡子為\,則往東,否則往西。依次類推找出所有反射鏡子的個數。