主題

ZeroJudge - b604: Center of Symmetry 解題心得

Not In My Back Yard | 2020-10-31 00:00:02 | 巴幣 0 | 人氣 49

題目連結:


題目大意:
輸入有多筆測試資料。每筆第一列給定一正整數 n (1 ≦ n ≦ 10000,當 n = 0 時代表輸入結束),代表一個標準座標平面上有 n 個點。接著有 n 列輸入,每列給定兩整數 x 、 y (-10000000 ≦ x 、 y ≦ 10000000),代表其中一個點的座標。

試問這 n 個點是否有對稱中心,即存在一點 s 滿足任意一點 p 都存在一點 q 使得點 s 到點 p 的距離 = 點 s 到點 q 的距離。

以下是範例輸入的圖示:



範例輸入:
8
1 10
3 6
6 8
6 2
3 -4
1 0
-2 -2
-2 4
0


範例輸出:
yes


解題思維:
因為對稱中心保證坐落於重心。因此我們只要檢查重心是不是對稱中心即可。

而重心的 x 座標可由所有點的 x 座標之總和除以點的個數 n 而得到。同理,重心的 y 座標也可快速求出。以下稱重心為點 C(cx, cy)。

接著我們將給定的所有點先依照 x 座標由小到大排(大到小也可以),然後對於 x 座標值一樣的再依據 y 座標由小到大排。

再來我們宣告一個長度為 n (對應點的個數)的布林陣列,代表每個點是否存在對稱點。

然後我們掃過每個點,判斷現在看到的這個點(假設為點 P(x, y))目前有沒有與之配對的對稱點。有的話就跳到下一個點;反之,則我們計算其對稱點 S(2cx - x, 2cy - y),之後看看 S 是否存在於給定的 n 個點之中,而這邊可以使用二分搜尋法(剛剛有排序,所以可以用)快速判斷其存在性。存在的話,就將點 P 以及點 S 都設為有對稱點;但如果不存在就代表重心一定不是對稱中心。

不過因為給定的點都是整數點,所以最好將上面求得的對稱點 S 之座標也轉為整數(進位或捨去至最接近的整數)再做判斷較佳。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作