Question

1037. 有效的回旋镖

English Version

题目描述

给定一个数组

 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)$。

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)

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);
  }
}

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);
  }
};

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)
}

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);
}

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)
  }
}