#30874: 解題報告


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [140.114.59.162]
最後登入時間 :
2024-11-13 00:16:45
i378. 垂直對稱 (Symmetry) -- TOI練習賽202205新手組第3題 | From: [163.27.13.193] | 發表日期 : 2022-06-18 14:42

 想法:把所有點按照x軸sort

我們知道,如果答案是success的話,那麼每個點一定都能找到一個對稱點。

假設今天有四個點,在同一個x軸上。(1,1),(1,2),(1,3),(1,4)

如果是有解的話,那x=1上最上面的點與最下面的點一定互為對稱點。那我們就可以判斷出那條水平線的y,也就是y=(y_max+y_min)/2

根據一點邏輯,可以知道,如果有一個點無法透過這條水平線找到對稱點的話,那麼就可以直接輸出failure。

 

找到那條線後,要如何判斷是否有對稱點呢?

我會建一個bool陣列,紀錄每個座標上是否有點。因為x,y有可能是負的,所以每個點x和y統一平移1000 ex :(0,-100)->(1000,900)

稍微數學推理一下,要如何判斷兩個點的對稱軸是否等於我們抓出來的那條對稱軸。可以知道y_max+y_min=y_a+y_b  // y_max,y_min:我們抓出來的兩個點

// y_a:目前要判斷的點 , y_b: 需要驗證是否存在的點

移項一下,就可以知道目前要找的這個點的x,y座標囉! 然後透過bool 陣列,O(1)就可以知道是否存在了

 

 

special case:

如果找不到同一個x軸上有兩個點的話,我會直接假設第一個點的y是我們要找的水平線,然後用原本找對稱點的部分下去跑就好。

 
ZeroJudge Forum