题目描述：

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.

题目大意：

给定平面上的4个点，判断是否围成一个正方形。

注意：

1. 坐标的范围[-10000, 10000]
2. 有效的正方形有4条相等的长度为正数的边，并且四个内角为直角。
3. 输入点无序

解题思路：

记4个点中最左下方的点为lb

以lb为极点对其余点进行极坐标排序，记排序后的点为pts

判断pts[0] - pts[1]; pts[1] - pts[2]; pts[2] - pts[3]; pts[3] - pts[0]是否距离为0

判断pts[0] - pts[1]; pts[1] - pts[2]; pts[2] - pts[3]; pts[3] - pts[0]是否相等

判断pts[0] - pts[1]平方的二倍是否等于pts[0] - pts[2]

Python代码：

class Solution(object):
    def validSquare(self, p1, p2, p3, p4):
        """
        :type p1: List[int]
        :type p2: List[int]
        :type p3: List[int]
        :type p4: List[int]
        :rtype: bool
        """
        pts = [p1, p2, p3, p4]
        lb = min(pts)
        ccw = lambda p1, p2, p3: (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])
        dsquare = lambda p1, p2: (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
        cmp = lambda p, q: ccw(lb, q, p) or dsquare(p, lb) - dsquare(q, lb)
        pts.sort(cmp)
        if not all(dsquare(pts[i], pts[j]) for i, j in zip((0, 1, 2, 3), (1, 2, 3, 0))): return False
        if len(set(dsquare(pts[i], pts[j]) for i, j in zip((0, 1, 2, 3), (1, 2, 3, 0)))) > 1: return False
        return dsquare(pts[0], pts[1]) * 2 == dsquare(pts[0], pts[2])

 

本文链接：http://bookshadow.com/weblog/2017/05/21/leetcode-valid-square/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码