题目地址:https://leetcode.com/problems/valid-square/description/

题目描述:

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

Thecoordinate (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、 Alltheinputintegersareintherange[-10000,10000].;
2、 Avalidsquarehasfourequalsideswithpositivelengthandfourequalangles(90-degreeangles).;
3、 Inputpointshavenoorder.;

题目大意

给出4个点,看能不能构成正方形。

解题方法

数学问题还得数学好才行。我们想一想,肯定要按照边来判断。一个四边形有6条边,如果是正方形的话需要满足,4条相等的短边,以及两边相等的对角线边。

所以我们计算一下边的长度,然后判断一下是否只有两类边即可。注意四边形没有长度为0的边。

时间复杂度是O(1),空间复杂度是O(1).

代码如下:

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
        """
        def d(point1, point2):
            return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2
        s = set([d(p1, p2), d(p1, p3), d(p1, p4), d(p2, p3), d(p2, p4), d(p3, p4)])
        return 0 not in s and len(s) == 2

1 2 3 4 5 6 7 8 9 10 11 12 13

参考资料:

https://leetcode.com/problems/valid-square/discuss/103442/C++-3-lines-(unordered_set)

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发