难度中等131
给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。
点的坐标 pi 表示为 [xi, yi] 。输入 不是 按任何顺序给出的。
一个 有效的正方形 有四条等边和四个等角(90度角)。
示例 1:
1
2
| 输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
|
示例 2:
1
2
| 输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false
|
示例 3:
1
2
| 输入：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
题解
四个点两两组合有6中组合，也就是可以通过四个点得到六条线段的长度，计算得到六条线段的长度，按从小到大排序，则如果是正方形，则有，前四条线段长度相等，后两条线段长度相等，即四边长相等，对象线相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
if (p1[0] == p2[0] && p1[1] == p2[1])
return false;
long[] l = new long[6];
l[0] = distance(p1, p2);
l[1] = distance(p1, p3);
l[2] = distance(p1, p4);
l[3] = distance(p2, p3);
l[4] = distance(p2, p4);
l[5] = distance(p3, p4);
Arrays.sort(l);
return l[0] == l[1] && l[0] == l[2] && l[0] == l[3] && l[0] == l[3] && l[4] == l[5];
}
public long distance(int[] p1, int[] p2) {
return (long) (p1[0] - p2[0]) * (p1[0] - p2[0]) + (long) (p1[1] - p2[1]) * (p1[1] - p2[1]);
}
}
|
- 时间复杂度：$O(l)$
- 空间复杂度：$O(l)$
