『LeetCode』1037 有效的回旋镖

题目

1037. 有效的回旋镖

给定一个数组 points ，其中 points[i] = [x^{i}, y^{i}] 表示 X-Y 平面上的一个点，如果这些点构成一个回旋镖 则返回 true 。

回旋镖 定义为一组三个点，这些点 各不相同 且 不在一条直线上 。

示例 1：

输入：points = [[1,1],[2,3],[3,2]]
输出：true

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：false

提示：

points.length == 3
points[i].length == 2
0 < = xⁱ, yⁱ < = 100

题解

【有效的回旋镖】简单几何

几何

根据几何知识

|x⃗ × y⃗| = |x⃗||y⃗|sin < x⃗, y⃗>

即两向量平行，则叉乘为$\vec{0}$，若两向量都经过同一点，则可以进一步推出两向量共线，那么在有共同顶点的前提下，两向量不共线的充要条件是：

$$ \vec{x} \times \vec{y} \neq \vec{0} $$

在本题中，我们可以以其中一点为共同顶点，另外两点为另一顶点构造两个向量： x⃗ = (x₀ − x₁, y₀ − y₁), y⃗ = (x₀ − x₂, y₀ − y₂).

代入上式得：

$$ \begin{cases} (x_0 - x_1) \times (y_0 - y_2) \neq 0 \\ (y_0 - y_1) \times (x_0 - x_2) \neq 0 \end{cases} $$

# Code language: Python
class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        return (points[0][0] - points[1][0]) * (points[0][1] - points[2][1]) != (points[0][1] - points[1][1]) * (points[0][0] - points[2][0])

// Code language: Java
class Solution {
    public boolean isBoomerang(int[][] points) {
        return (points[0][0] - points[1][0]) * (points[0][1] - points[2][1]) != (points[0][1] - points[1][1]) * (points[0][0] - points[2][0]);
    }
}

// Code language: C++
class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        return (points[0][0] - points[1][0]) * (points[0][1] - points[2][1]) != (points[0][1] - points[1][1]) * (points[0][0] - points[2][0]);
    }
};

时间复杂度: O(1)
空间复杂度: O(1)

最后

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1037 有效的回旋镖

题目

标签

题解

几何

最后