LC.P593[有效的正方形]

题目描述

给定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
  • -104 <= xi, yi <= 104

方法一：数学

任取四个点中的三个点，若这三个点能组成等边直角三角形，则保存正方形的边长为直角边长，继续排列组合，若无法组成等边直角三角形或组成的边长与原有的边长不等，则返回false；若全部检查完成，返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    long length = -1;

    public boolean validSquare(int[] a, int[] b, int[] c, int[] d) {
        return check(a, b, c) && check(a, b, d) && check(a, c, d) && check(b, c, d);
    }

    /**
     * 判断三条边是否能组成等边直角三角形
     *
     * @return 结果
     */
    boolean check(int[] a, int[] b, int[] c) {
        long l1 = (long) (a[0] - b[0]) * (a[0] - b[0]) + (long) (a[1] - b[1]) * (a[1] - b[1]);
        long l2 = (long) (a[0] - c[0]) * (a[0] - c[0]) + (long) (a[1] - c[1]) * (a[1] - c[1]);
        long l3 = (long) (b[0] - c[0]) * (b[0] - c[0]) + (long) (b[1] - c[1]) * (b[1] - c[1]);
        boolean flag = (l1 == l2 && l1 + l2 == l3) || (l1 == l3 && l1 + l3 == l2) || (l2 == l3 && l2 + l3 == l1);
        if (!flag) return false;
        if (length == -1) length = Math.min(l1, l2);
        else return length != 0 && length == Math.min(l1, l2);
        return true;
    }
}
  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$