算法 - 有效的正方形

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

数学公式求解

---

题目来源

593. 有效的正方形 - 力扣（LeetCode）

题目描述

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

点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。

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

示例

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True

输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false

输入：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

题目解析

假设输入的四点分别为A,B,C,D，我们可以固定A点，然后求

AB长度、AC长度、AD长度，如果四点可以组成正方形，则必然有两条边的长度相等，且另一条边的平方 = 相等的两条边的各自平方之和。

但是以上判断还不足以判定四点可以形成正方形，我们还需要保证正方形的对角线垂直，如果AB,AC相等的话，则AD就是对角线，BC也是对角线。

我们可以通过向量内积为0来判断两个向量是否垂直，因此我们可以计算

(A.x - D.x) * (B.x - C.x) + (A.y - D.y) * (B.y - C.y) === 0

来判断对角线是否垂直。

若以上条件都满足，则说明是四点可以组成正方形。

另外，我们需要处理特殊情况，比如四点中有两点或者更多的点相同，此时就无法形成四边形，更别说形成正方形了，因此我们需要排除掉这些特殊情况。

算法源码

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function(p1, p2, p3, p4) {
    const set = new Set([p1,p2,p3,p4].map(p => p[0]+' '+p[1]))
    if(set.size < 4) return false
 
    let [x1, y1] = p1
    let [x2, y2] = p2
    let [x3, y3] = p3
    let [x4, y4] = p4
 
    let l12 = Math.pow(x2-x1, 2) + Math.pow(y2-y1,2)
    let l13 = Math.pow(x3-x1, 2) + Math.pow(y3-y1,2)
    let l14 = Math.pow(x4-x1, 2) + Math.pow(y4-y1,2)
 
    let v12 = [x2-x1, y2-y1]
    let v13 = [x3-x1, y3-y1]
    let v14 = [x4-x1, y4-y1]
 
    if(l12===l13 && l12 + l13===l14) {
        let v23 = [x3-x2, y3-y2]
        return isVertical(v14, v23)
    }
    else if(l12===l14 && l12 +l14===l13){
        let v24 = [x4-x2, y4-y2]
        return isVertical(v24, v13)
    }
    else if(l13===l14 && l13+l14===l12){
        let v34 = [x4-x3, y4-y3]
        return isVertical(v34, v12)
    }
    else {
        return false
    }
};
 
function isVertical(v1, v2) {
    return v1[0]*v2[0] + v1[1]*v2[1] === 0
}

数学公式求解

具体数学公式推导请看下面文章

算法 - 正方形数量_伏城之外的博客-CSDN博客

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function (p1, p2, p3, p4) {
  let arr = [p1, p2, p3, p4];
  const set = new Set(arr.map((p) => p[0] + " " + p[1]));
  if (set.size < 4) return false;
 
  let combination = [];
  dfs(4, 2, 0, [], combination);
 
  let flag = false;
  for (let i = 0; i < combination.length; i++) {
    let [x1, y1] = arr[combination[i][0]];
    let [x2, y2] = arr[combination[i][1]];
 
    let x3 = x1 - (y1 - y2);
    let y3 = y1 + (x1 - x2);
    let x4 = x2 - (y1 - y2);
    let y4 = y2 + (x1 - x2);
    if (set.has(x3 + " " + y3) && set.has(x4 + " " + y4)) {
      flag = true;
      break;
    }
 
    let x5 = x1 + (y1 - y2);
    let y5 = y1 - (x1 - x2);
    let x6 = x2 + (y1 - y2);
    let y6 = y2 - (x1 - x2);
    if (set.has(x5 + " " + y5) && set.has(x6 + " " + y6)) {
      flag = true;
      break;
    }
  }
 
  return flag;
};
 
function dfs(n, k, index, path, result) {
  if (path.length === k) {
    return result.push([...path]);
  }
 
  for (let i = index; i < n; i++) {
    path.push(i);
    dfs(n, k, i + 1, path, result);
    path.pop();
  }
}