【593. Valid Square】

来源：力扣（LeetCode）

描述：

给定2D空间中四个点的坐标 p1, p2, p3 和 p4,如果这四个点构成一个正方形,则返回 true .

点的坐标 pi 表示为 [xi, yi] .输入 不是 按任何顺序给出的.

一个 有效的正方形 有四条等边和四个等角(90度角).

示例 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

提示:

• p1.length == p2.length == p3.length == p4.length == 2
• -10⁴ <= xi, yi <= 10⁴

方法：数学

思路与算法

The square determination theorem is a determination theorem used in geometry to determine whether a quadrilateral is a square.The general order for identifying a square is to first state that it is a parallelogram;Again, it's a rhombus（或矩形）;The last statement is that it is a rectangle（或菱形）.Then we can judge by enumerating the two hypotenuses of the quadrilateral：

1. If the midpoints of the two hypotenuses are the same：Then it shows that the quadrilateral formed by the two hypotenuses is 「平行四边形」.
2. 在满足「条件一」的基础上,If the two hypotenuses are the same length：Then it shows that the quadrilateral formed by the two hypotenuses is 「矩形」.
3. 在满足「条件二」的基础上,If the two hypotenuses are perpendicular to each other：Then it shows that the quadrilateral formed by the two hypotenuses is 「正方形」.

代码：

class Solution {
    
public:
    bool checkLength(vector<int>& v1, vector<int>& v2) {
    
        return (v1[0] * v1[0] + v1[1] * v1[1]) == (v2[0] * v2[0] + v2[1] * v2[1]);
    }

    bool checkMidPoint(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
    
        return (p1[0] + p2[0]) == (p3[0] + p4[0]) && (p1[1] + p2[1]) == (p3[1] + p4[1]);
    }

    int calCos(vector<int>& v1, vector<int>& v2) {
    
        return (v1[0] * v2[0] + v1[1] * v2[1]) == 0;
    }

    bool help(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
    
        vector<int> v1 = {
    p1[0] - p2[0], p1[1] - p2[1]};
        vector<int> v2 = {
    p3[0] - p4[0], p3[1] - p4[1]};
        if (checkMidPoint(p1, p2, p3, p4) && checkLength(v1, v2) && calCos(v1, v2)) {
    
            return true;
        } 
        return false;
    }

    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
    
        if (p1 == p2) {
    
            return false;
        }
        if (help(p1, p2, p3, p4)) {
    
            return true;
        }
        if (p1 == p3) {
    
            return false;
        }
        if (help(p1, p3, p2, p4)) {
    
            return true;
        }
        if (p1 == p4) {
    
            return false;
        }
        if (help(p1, p4, p2, p3)) {
    
            return true;
        }
        return false;
    }
};

执行用时：4 ms, 在所有 C++ 提交中击败了75.76%的用户
内存消耗：25.8 MB, 在所有 C++ 提交中击败了69.97%的用户
复杂度分析
时间复杂度：O(1).
空间复杂度：O(1),仅使用常数变量.