Skip to content

Latest commit

 

History

History
149 lines (109 loc) · 3.72 KB

File metadata and controls

149 lines (109 loc) · 3.72 KB
comments difficulty edit_url rating source tags
true
简单
1255
第 135 场周赛 Q1
几何
数组
数学

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

Python3

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)

Java

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

C++

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

Go

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

TypeScript

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

Rust

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