題目
題目鏈接：593. 有效的正方形
題意：給出二維平面上四個點的坐標，判斷這四個點是否能構成一個正方形，四個點的輸入順序不做任何保證，
思路
通過向量運算可以很輕松地解決這道題，任取一點向其他三點連線，可以得到三個向量，我們將這三個向量按照其長度從小到大排序，分別稱為 \(\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; // 構成正方形
}
}
這種使用向量運算的解法有兩個好處：
- 只需要對向量做一次排序即可解決頂點不按順序的問題，不需要分類討論，較為簡潔，
- 全程都是整數運算，不需要擔心浮點運算帶來的舍入誤差，
本題還有其他做法：
- 檢查四邊形的兩條斜邊
- 對頂點做旋轉變換
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502467.html
標籤：其他