跳转至

1037. 有效的回旋镖

题目描述

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 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 <= xi, yi <= 100

解法

方法一：斜率比较

设三点分别为 $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$。两点之间斜率计算公式为 $\frac{y_2-y_1}{x_2-x_1}$。

要使得三点不共线，需要满足 $\frac{y_2-y_1}{x_2-x_1}\neq\frac{y_3-y_2}{x_3-x_2}$，我们将式子变形得到 $(y_2-y_1)(x_3-x_2) \neq (y_3-y_2)(x_2-x_1)$。

注意：

  1. 当两点之间斜率不存在，即 $x_1=x_2$，上述变式仍然成立；
  2. 若斜率除法运算比较存在精度问题，同样可以变换为乘法。

时间复杂度 $O(1)$。

1
2
3
4
class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        (x1, y1), (x2, y2), (x3, y3) = points
        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1)

1
2
3
4
5
6
7
8
class Solution {
    public boolean isBoomerang(int[][] points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1);
    }
}

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        return (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1);
    }
};

1
2
3
4
5
6
func isBoomerang(points [][]int) bool {
    x1, y1 := points[0][0], points[0][1]
    x2, y2 := points[1][0], points[1][1]
    x3, y3 := points[2][0], points[2][1]
    return (y2-y1)*(x3-x2) != (y3-y2)*(x2-x1)
}

1
2
3
4
5
6
function isBoomerang(points: number[][]): boolean {
    const [x1, y1] = points[0];
    const [x2, y2] = points[1];
    const [x3, y3] = points[2];
    return (x1 - x2) * (y2 - y3) !== (x2 - x3) * (y1 - y2);
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn is_boomerang(points: Vec<Vec<i32>>) -> bool {
        let (x1, y1) = (points[0][0], points[0][1]);
        let (x2, y2) = (points[1][0], points[1][1]);
        let (x3, y3) = (points[2][0], points[2][1]);
        (x1 - x2) * (y2 - y3) != (x2 - x3) * (y1 - y2)
    }
}

评论