LeetCode 593. 有效的正方形（向量做法）

zhb2000 2023-03-28 原文

题目

题意：给出二维平面上四个点的坐标，判断这四个点是否能构成一个正方形，四个点的输入顺序不做任何保证。

思路

通过向量运算可以很轻松地解决这道题。任取一点向其他三点连线，可以得到三个向量。我们将这三个向量按照其长度从小到大排序，分别称为 $\boldsymbol{v}_0, \boldsymbol{v}_1, \boldsymbol{v}_2$，若满足以下三个条件，则 $\boldsymbol{v}_0, \boldsymbol{v}_1, \boldsymbol{v}_2$ 可以“张出”一个正方形（见下图）：

$\boldsymbol{v}_0 + \boldsymbol{v}_1 = \boldsymbol{v}_2$（四点构成平行四边形）
$\Vert\boldsymbol{v}_0\Vert = \Vert\boldsymbol{v}_1\Vert$（平行四边形 + 邻边相等，此时四点构成菱形）
$\boldsymbol{v}_0 \cdot \boldsymbol{v}_1 = 0$（菱形 + 直角，此时四点构成正方形）

我们还需要特别注意排除点重合的情况，例如四个点全部重合在一起，此时上面的三个条件仍然满足，但是不能构成正方形。

代码

以下为 Rust 语言的题解代码。

首先我们需要定义一个二维向量类型：

/// 二维向量
#[derive(Copy, Clone, Eq, PartialEq)]
struct Vector {
    x: i32,
    y: i32
}

impl Vector {
    fn new(from: (i32, i32), to: (i32, i32)) -> Self { Vector { x: to.0 - from.0, y: to.1 - from.1 } }
    /// 向量的模的平方
    fn len2(&self) -> i32 { self.x * self.x + self.y * self.y }
}

impl std::ops::Mul for Vector {
    type Output = i32;
    /// 向量点乘
    fn mul(self, rhs: Self) -> Self::Output { self.x * rhs.x + self.y * rhs.y }
}

impl std::ops::Add for Vector {
    type Output = Vector;
    /// 向量加法
    fn add(self, rhs: Self) -> Self::Output { Vector { x: self.x + rhs.x, y: self.y + rhs.y } }
}

解题函数如下：

impl Solution {
    pub fn valid_square(p1: Vec<i32>, p2: Vec<i32>, p3: Vec<i32>, p4: Vec<i32>) -> bool {
        let mut v = [
            Vector::new((p1[0], p1[1]), (p2[0], p2[1])),
            Vector::new((p1[0], p1[1]), (p3[0], p3[1])),
            Vector::new((p1[0], p1[1]), (p4[0], p4[1]))
        ];
        v.sort_by_key(Vector::len2);
        return v[0].len2() > 0            // 点不重合
            && v[0] + v[1] == v[2]        // 构成平行四边形
            && v[0].len2() == v[1].len2() // 构成菱形
            && v[0] * v[1] == 0;          // 构成正方形
    }
}

这种使用向量运算的解法有两个好处：

只需要对向量做一次排序即可解决顶点不按顺序的问题，不需要分类讨论，较为简洁。
全程都是整数运算，不需要担心浮点运算带来的舍入误差。

本题还有其他做法：

LeetCode 做法 boldsymbol Vector self 算法与数据结构

有关LeetCode 593. 有效的正方形（向量做法）的更多相关文章

ruby - 如何进行排列以有效地定制输出 - 2
这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][
Python 刷Leetcode题库，顺带学英语单词（31） - 2
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
python - 是否可以使用 Ruby 或 Python 禁用 anchor /引用来发出有效的 YAML？ - 2
是否可以在PyYAML或Ruby的Psych引擎中禁用创建anchor和引用(并有效地显式列出冗余数据)？也许我在网上搜索时遗漏了一些东西，但在Psych中似乎没有太多可用的选项，而且我也无法确定PyYAML是否允许这样做.基本原理是我必须序列化一些数据并将其以可读的形式传递给一个不是真正的技术同事进行手动验证。有些数据是多余的，但我需要以最明确的方式列出它们以提高可读性(anchor和引用是提高效率的好概念，但不是人类可读性)。Ruby和Python是我选择的工具，但如果有其他一些相当简单的方法来“展开”YAML文档，它可能就可以了。最佳答案
ruby - 为什么这个救援语法有效？ - 2
好的，所以我有了我正在使用的应用程序的这种方法，它可以在生产中使用。我的问题为什么这行得通？这是新的Ruby语法吗？defeditload_elements(current_user)unlesscurrent_user.role?(:admin)respond_todo|format|format.json{render:json=>@user}format.xml{render:xml=>@user}format.htmlendrescueActiveRecord::RecordNotFoundrespond_to_not_found(:json,:xml,:html)end
ruby - 奇怪的 ruby for 循环行为(为什么这样做有效) - 2
defreverse(ary)result=[]forresult[0,0]inaryendresultendassert_equal["baz","bar","foo"],reverse(["foo","bar","baz"])这行得通，我想了解原因。有什么解释吗？最佳答案如果我使用each而不是for/in重写它，它看起来像这样:defreverse(ary)result=[]#forresult[0,0]inaryary.eachdo|item|result[0,0]=itemendresultendforainb基本上就
arrays - 在两个数组中查找不相交元素的有效方法是什么？ - 2
我有以下数组:A=[1,2,3,4,5]B=[2,6,7,1]我想找到不相交的元素，如下:output=[3,4,5,6,7]我是这样实现的，output=A+B-(A&B)但它效率低下，因为我添加了两个数组，然后删除了公共(public)元素。它类似于查找不相交的元素。我能做得比这更好吗？如果是，怎么办？最佳答案如何只选择A中的元素而不是B中的元素以及B中的元素而不是A中的元素。(A-B)+(B-A) 关于arrays-在两个数组中查找不相交元素的有效方法是什么？，我们在Stack
ruby - 为什么 `middleman serve` 有效，但是 `middleman build` 编译这个 Sass 失败？ - 2
当我刚刚运行middleman时服务，all.css编译得很好，只包含对+box-shadow(none)的调用:/*line1,/home/yang/asdf/source/stylesheets/content.css.sass*/div{-webkit-box-shadow:none;-moz-box-shadow:none;box-shadow:none;}但是当我构建网站时，我得到了这个Sass/Compass错误:$middlemanbuildSlim::EmbeddedEngineisdeprecated,itiscalledSlim::EmbeddedinSlim2.0
IDEA使用LeetCode插件 - 2
前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit
ruby - 在公差范围内确定两条线段是否属于同一线段的最有效方法是什么？ - 2
编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段f(fx0,fy0)和(fx1,fy1)和g(gx0,gy0)和(gx1,gy1)这些来自计算机视觉算法边缘检测器之类的东西，在某些情况下，两条线基本相同，但由于像素容差而被视为两条不同的线。有几种情况f和g共享完全相同的端点，例如:f=(0,0),(10,10)g=(0,0),(10,10)f和g共享大致相同的端点和大致相同的长度，例如:f=(0,0.01
ruby - 如何检查一个值是否是 Integer()、Float() 或 Rational() 的有效输入？ - 2
这大致基于“HowtoconvertaStringtoIntegerorFloat”。如果我想使用Ruby的内置转换机制将数字字符串输入转换为其“最合适的类型”，我可以这样做:defconvert(input)value=Integer(input)rescuenilvalue||=Float(input)rescuenilvalue||=Rational(input)rescuenilvalueendconvert('1')#=>1convert('1_000')#=>1000convert('0xff')#=>255convert('0.5')#=>0.5convert('1e2'

LeetCode 593. 有效的正方形（向量做法）

题目

思路

代码

有关LeetCode 593. 有效的正方形（向量做法）的更多相关文章

随机推荐