問題概要

LeetCodeの問題593では、2次元平面上の4点の座標が与えられ、それらが正方形を形成するかどうかを判定する必要がある。入力される点の順序は任意である。

解法の考え方

ベクトル演算を利用することで効率的に解決できる。基準点を1つ選び、他の3点へのベクトルを計算する。これらのベクトルを長さの昇順に並べ替え、\(\boldsymbol{v}_0, \boldsymbol{v}_1, \boldsymbol{v}_2\)とする。以下の条件が満たされるとき、正方形を形成する：

1. \(\boldsymbol{v}_0 + \boldsymbol{v}_1 = \boldsymbol{v}_2\)（平行四辺形条件）
2. \(\Vert\boldsymbol{v}_0\Vert = \Vert\boldsymbol{v}_1\Vert\)（ひし形条件）
3. \(\boldsymbol{v}_0 \cdot \boldsymbol{v}_1 = 0\)（直交条件）

注意点として、全ての点が同一座標の場合（ベクトル長が0）を除外する必要がある。

実装例

Rust言語による実装例を示す。まずベクトル型を定義する：

/// 2次元ベクトル構造体
#[derive(Copy, Clone, Eq, PartialEq)]
struct Vec2D {
    dx: i32,
    dy: i32
}

impl Vec2D {
    fn create(start: (i32, i32), end: (i32, i32)) -> Self {
        Vec2D { dx: end.0 - start.0, dy: end.1 - start.1 }
    }
    
    /// ベクトルの長さの二乗
    fn squared_length(&self) -> i32 {
        self.dx * self.dx + self.dy * self.dy
    }
}

impl std::ops::Mul for Vec2D {
    type Output = i32;
    /// 内積演算
    fn mul(self, other: Self) -> i32 {
        self.dx * other.dx + self.dy * other.dy
    }
}

impl std::ops::Add for Vec2D {
    type Output = Vec2D;
    /// ベクトル加算
    fn add(self, other: Self) -> Vec2D {
        Vec2D { dx: self.dx + other.dx, dy: self.dy + other.dy }
    }
}

判定関数の実装：

impl Solution {
    pub fn is_valid_square(p1: Vec<i32>, p2: Vec<i32>, p3: Vec<i32>, p4: Vec<i32>) -> bool {
        let mut vectors = [
            Vec2D::create((p1[0], p1[1]), (p2[0], p2[1])),
            Vec2D::create((p1[0], p1[1]), (p3[0], p3[1])),
            Vec2D::create((p1[0], p1[1]), (p4[0], p4[1]))
        ];
        
        vectors.sort_by_key(|v| v.squared_length());
        
        vectors[0].squared_length() > 0 &&           // 点が重複していない
            vectors[0] + vectors[1] == vectors[2] && // 平行四辺形条件
            vectors[0].squared_length() == vectors[1].squared_length() && // ひし形条件
            vectors[0] * vectors[1] == 0            // 直交条件
    }
}

この解法の利点：

• ベクトルのソートにより頂点順序の問題を回避
• 浮動小数点演算を使わず整数演算のみで処理
• 幾何学的条件を明確に表現

代替解法として以下のアプローチも可能：

• 対角線の性質を利用する方法
• 座標変換を適用する方法