天天看點

LeetCode 593. Valid Square 平面四點能否正方形

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True
      

Note:

  1. All the input integers are in the range [-10000, 10000].
  2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  3. Input points have no order.

---------------------------------------

隻考慮邊長的關系,這題的寫法就簡化了一半,如果涉及到斜率寫起來比較煩。。。

既然隻考慮邊長,那麼會有兩種思路:

思路一:枚舉6個定點中兩兩點之間的長度,正方形最後隻有2種長度,同時不包含為0的長度。證明可以從挑兩兩相等的邊去考慮。

class Solution:
    def validSquare(self, p1,p2,p3,p4) -> bool:
        def dis(x,y):
            xdis,ydis=x[0]-y[0],x[1]-y[1]
            return xdis*xdis+ydis*ydis
        d12,d13,d14,d23,d24,d34=dis(p1,p2),dis(p1,p3),dis(p1,p4),dis(p2,p3),dis(p2,p4),dis(p3,p4)
        dset = {d12,d13,d14,d23,d24,d34}
        return len(dset) == 2 and 0 not in dset
           

思路二:把4個點按橫坐标、縱坐标排序,發現正方形排序後隻有兩種情況,那麼判斷這兩種情況就可以:

LeetCode 593. Valid Square 平面四點能否正方形
class Solution:
    def validSquare(self, p1,p2,p3,p4) -> bool:
        def dis(x,y):
            xdis,ydis=x[0]-y[0],x[1]-y[1]
            return xdis*xdis+ydis*ydis
        pp = sorted([p1,p2,p3,p4])
        d01,d13,d23,d02,d12,d03=dis(pp[0],pp[1]),dis(pp[1],pp[3]),dis(pp[2],pp[3]),dis(pp[0],pp[2]),dis(pp[1],pp[2]),dis(pp[0],pp[3])
        return d01>0 and d01==d13 and d13==d23 and d23==d02 and d12==d03