【每日一题】- 2019-08-19 - 593. 有效的正方形

[azl397985856]

【每日一题】- 2019-08-19 - 593. 有效的正方形

[raof01]

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        auto dists = vector<unsigned int>(6);
        dists[0] = squareDist(p1, p2);
        dists[1] = squareDist(p2, p3);
        dists[2] = squareDist(p3, p4);
        dists[3] = squareDist(p4, p1);
        dists[4] = squareDist(p1, p3);
        dists[5] = squareDist(p2, p4);
        auto sum = accumulate(dists.begin(), dists.end(), 0);
        auto cnt = 0;
        auto cnt1 = 0;
        for (auto v : dists) {
            if (sum == 8 * v) ++cnt;
            else if (sum == 4 * v) ++cnt1;
        }
        return cnt == 4 && cnt1 == 2;
    }
private:
    unsigned int squareDist(const vector<int>& p1, const vector<int>& p2) {
        auto deltaX = p1[0] - p2[0];
        auto deltaY = p1[1] - p2[1];
        return deltaX * deltaX + deltaY * deltaY;
    }
};

[azl397985856]

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        auto dists = vector<unsigned int>(6);
        dists[0] = squareDist(p1, p2);
        dists[1] = squareDist(p2, p3);
        dists[2] = squareDist(p3, p4);
        dists[3] = squareDist(p4, p1);
        dists[4] = squareDist(p1, p3);
        dists[5] = squareDist(p2, p4);
        auto sum = accumulate(dists.begin(), dists.end(), 0);
        auto cnt = 0;
        auto cnt1 = 0;
        for (auto v : dists) {
            if (sum == 8 * v) ++cnt;
            else if (sum == 4 * v) ++cnt1;
        }
        return cnt == 4 && cnt1 == 2;
    }
private:
    unsigned int squareDist(const vector<int>& p1, const vector<int>& p2) {
        auto deltaX = p1[0] - p2[0];
        auto deltaY = p1[1] - p2[1];
        return deltaX * deltaX + deltaY * deltaY;
    }
};

这里的数学原理和公式是什么

[xiongcaihu]

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 * 
 * 计算任意两点的距离，4个点一共生成6个结果
 * 对这些结果排序，正方形满足 前四个相同，后两个相同
 */
var validSquare = function (p1, p2, p3, p4) {
    var sum = [temp(p1, p2), temp(p1, p3), temp(p1, p4), temp(p2, p3), temp(p2, p4), temp(p3, p4)];
    sum.sort((a, b) => a - b);

    return sum[0] == sum[3] && sum[0] != 0 && sum[4] == sum[5];

    function temp(a, b) {
        return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
    }
};

执行结果：通过
显示详情 执行用时 :76 ms , 在所有 JavaScript 提交中击败了 84.62% 的用户
内存消耗 : 33.9 MB, 在所有 JavaScript 提交中击败了 70.00% 的用户

[azl397985856]

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 * 
 * 计算任意两点的距离，4个点一共生成6个结果
 * 对这些结果排序，正方形满足 前四个相同，后两个相同
 */
var validSquare = function (p1, p2, p3, p4) {
    var sum = [temp(p1, p2), temp(p1, p3), temp(p1, p4), temp(p2, p3), temp(p2, p4), temp(p3, p4)];
    sum.sort((a, b) => a - b);

    return sum[0] == sum[3] && sum[0] != 0 && sum[4] == sum[5];

    function temp(a, b) {
        return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
    }
};

执行结果：通过
显示详情 执行用时 :76 ms , 在所有 JavaScript 提交中击败了 84.62% 的用户
内存消耗 : 33.9 MB, 在所有 JavaScript 提交中击败了 70.00% 的用户

排序是多余的。

另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

[azl397985856]

✔ Accepted
✔ 244/244 cases passed (48 ms)
✔ Your runtime beats 100 % of javascript submissions
✔ Your memory usage beats 100 % of javascript submissions (34.1 MB)

[azl397985856]

模仿 @raof01 的思路写的JS代码，

基本思路就是： 证明四个角都是直角， 而证明直角的方式就是边长关系。

四个点一共有六个连接的线段，其中两个是对角线，另外四个是边。

对于直角来说，满足“a * a + b * b = c * c”, 由于是正方形，所以a = b， 因此c就等于
2 * a * a , 其中a为边长，c就是对角线的长度。

我们分别计算出距离的平方，如果有四个相同，另外两个相同。 且二者的关系可以满足直角，那么他就有四个直角，他就是一个正方形

/*
 * @lc app=leetcode id=593 lang=javascript
 *
 * [593] Valid Square
 */
function square(p1, p2) {
    const deltaX = p1[0] - p2[0];
    const deltaY = p1[1] - p2[1];

    return deltaX * deltaX + deltaY * deltaY;
}
/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function (p1, p2, p3, p4) {
  // 证明四个角都是直角
  // 证明直角的方式就是边长关系
  const squares = [
    square(p1, p2),
    square(p1, p3),
    square(p1, p4),
    square(p2, p3),
    square(p2, p4),
    square(p3, p4)
  ];
  let cnt1 = 0;
  let cnt2 = 0;
  let sum = 0;

  for(let i = 0; i < squares.length; i++) {
    sum += squares[i];
  }

  for(let i = 0; i < squares.length; i++) {
      if (sum === 8 * squares[i]) {
          cnt1++;
      } else if(sum === 4 * squares[i]) {
          cnt2++;
      }
  }

  return cnt1 === 4 && cnt2 ===2;
  
}

[Sean-lxy]

/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 * 
 * 计算任意两点的距离，4个点一共生成6个结果
 * 对这些结果排序，正方形满足 前四个相同，后两个相同
 */
var validSquare = function (p1, p2, p3, p4) {
    var sum = [temp(p1, p2), temp(p1, p3), temp(p1, p4), temp(p2, p3), temp(p2, p4), temp(p3, p4)];
    sum.sort((a, b) => a - b);

    return sum[0] == sum[3] && sum[0] != 0 && sum[4] == sum[5];

    function temp(a, b) {
        return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;
    }
};

执行结果：通过
显示详情 执行用时 :76 ms , 在所有 JavaScript 提交中击败了 84.62% 的用户
内存消耗 : 33.9 MB, 在所有 JavaScript 提交中击败了 70.00% 的用户

排序是多余的。

另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

需要排序的吧，因为给定参数对应点的顺序是不一定的，所以要先把对角线排序到最后，判断。

四条边相等且对角线相等，就是正方形

[raof01]

排序是多余的。
另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

需要排序的吧，因为给定参数对应点的顺序是不一定的，所以要先把对角线排序到最后，判断。

四条边相等且对角线相等，就是正方形

不需要排序的

[Sean-lxy]

排序是多余的。
另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

需要排序的吧，因为给定参数对应点的顺序是不一定的，所以要先把对角线排序到最后，判断。
四条边相等且对角线相等，就是正方形

不需要排序的

如果不排序，根本不能确定sum的哪一项为对角线或者边线

[azl397985856]

排序是多余的。
另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

需要排序的吧，因为给定参数对应点的顺序是不一定的，所以要先把对角线排序到最后，判断。
四条边相等且对角线相等，就是正方形

不需要排序的

如果不排序，根本不能确定sum的哪一项为对角线或者边线

看上面我的解法

[Sean-lxy]

排序是多余的。
另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

需要排序的吧，因为给定参数对应点的顺序是不一定的，所以要先把对角线排序到最后，判断。
四条边相等且对角线相等，就是正方形

不需要排序的

如果不排序，根本不能确定sum的哪一项为对角线或者边线

看上面我的解法

在 @xiongcaihu 的这种解法里，排序是必须的，不也是一直讨论这种嘛

[azl397985856]

排序是多余的。
另外显然正方形有这个性质，但是有这个性质的一定是正方形么？如果是的话怎么证明

需要排序的吧，因为给定参数对应点的顺序是不一定的，所以要先把对角线排序到最后，判断。
四条边相等且对角线相等，就是正方形

不需要排序的

如果不排序，根本不能确定sum的哪一项为对角线或者边线

看上面我的解法

在 @xiongcaihu 的这种解法里，排序是必须的，不也是一直讨论这种嘛

他的解法和我的有差别么

[azl397985856]

https://github.com/azl397985856/leetcode/blob/master/daily/2019-08-19.md