前往
大廳
主題

LeetCode - 593. Valid Square 解題心得

Not In My Back Yard | 2021-08-16 00:00:01 | 巴幣 2 | 人氣 161

題目連結:


題目意譯:
給定二維平面中四個點 p1 、 p2 、 p3 和 p4 的座標,回傳真(True)如果四個點可形成一個正方形。

一個點 pi 的座標表示為 [xi, yi]。輸入不會以任意特定順序給定。

一個合法的正方形有著四條相同的正整數邊長的邊以及四個相同角度(90 度)的角。

限制:
p1.length == p2.length == p3.length == p4.length == 2
-10 ^ 4 <= xi 、 yi <= 10 ^ 4



範例測資:
範例 1:
輸入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
輸出: true

範例 2:
輸入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
輸出: false

範例 3:
輸入: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
輸出: true


解題思維:
將這四個點先按照 X 座標由小到大排序,X 座標一樣再按照 Y 座標由小到大排序,然後重新編號。

因此現在 p1 為最左下的點、p4 為最右上的點。而現在如果這四個點會形成正方形,則邊 p1p2 的長度將等於邊 p2p4 、邊 p3p4 、邊 p1p3 的長度。而邊長可以藉由著兩點距離公式(參見維基頁面之說明)求得。

而因為正方形的四個角相等或且唯若兩條對角線長度相同(四條邊等長上面已經判斷過了)。而兩條對角線為邊 p1p4 和邊 p2p3 這兩個邊,一樣用距離公式求得距離值判斷即可。

當給定的四個點都符合以上條件時,則代表這四個點可以形成一個合法的正方形;反之則不行。




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

創作回應

相關創作

更多創作