侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学, 几何】有效的正方形

GabrielxD
2022-07-29 / 0 评论 / 0 点赞 / 71 阅读 / 484 字 / 正在检测是否收录...

题目

593. 有效的正方形


给定2D空间中四个点的坐标 p1, p2, p3p4,如果这四个点构成一个正方形,则返回 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^4 <= xi, yi <= 10^4

解题

方法一:数学 几何

思路

如果一个平面图形是正方形,那么它有且只有两种不同的长度:

  • 四条边长
  • 两条对角线 (2边长\sqrt{2} \cdot 边长)

现在已知四个顶点,算出它们两两之间的距离并加入集合,最后集合长度为 2 且不含 0 就是一个有效的正方形。

代码

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<Integer> set = new HashSet<Integer>(){{
            this.add(getDistancePow(p1, p2));
            this.add(getDistancePow(p1, p3));
            this.add(getDistancePow(p1, p4));
            this.add(getDistancePow(p2, p3));
            this.add(getDistancePow(p2, p4));
            this.add(getDistancePow(p3, p4));
        }};
        return !set.contains(0) && set.size() == 2;
    }

    private int getDistancePow(int[] a, int[] b) {
        return (int) (Math.pow(Math.abs(a[0] - b[0]), 2) + Math.pow(Math.abs(a[1] - b[1]), 2));
    }
}
class Solution {
private:
    int get_distance_square(vector<int>& a, vector<int>& b) {
        return pow(abs(a[0] - b[0]), 2) + pow(abs(a[1] - b[1]), 2);
    }

public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        unordered_set<int> st = {
            get_distance_square(p1, p2),
            get_distance_square(p1, p3),
            get_distance_square(p1, p4),
            get_distance_square(p2, p3),
            get_distance_square(p2, p4),
            get_distance_square(p3, p4)
        };
        return !st.count(0) && st.size() == 2;
    }
};
0

评论区