『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^{i}, y^{i} <= 100\)

题解

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

几何

根据几何知识

\[ | \vec{x} \times \vec{y} | = | \vec{x} | | \vec{y} | \sin <\vec{x}, \vec{y}> \]

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

\[ \vec{x} \times \vec{y} \neq \vec{0} \]

在本题中，我们可以以其中一点为共同顶点，另外两点为另一顶点构造两个向量： \(\vec{x} = (x_0 - x_1, y_0 - y_1)\), \(\vec{y} = (x_0 - x_2, y_0 - y_2)\).

代入上式得：

\[ \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 有效的回旋镖

题目

标签

题解

几何

最后