Valid Boomerang

easy geometry cross product math

Problem

Given an array points where points[i] = [x_i, y_i] represents three points on a plane, return true if these points form a boomerang. A boomerang is a set of three points that are all distinct and not in a straight line.

Inputpoints = [[1, 1], [2, 3], [3, 2]]

Outputtrue

The three points are distinct and not collinear, so they form a boomerang.

points (3 pairs, e.g. "1 1, 2 3, 3 2")

def is_boomerang(points):
    (x1, y1), (x2, y2), (x3, y3) = points
    cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
    return cross != 0

function isBoomerang(points) {
  const [[x1, y1], [x2, y2], [x3, y3]] = points;
  const cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
  return cross !== 0;
}

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];
        int cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
        return cross != 0;
    }
}

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];
    int cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    return cross != 0;
}

Explanation

Three points form a boomerang only when they are not on a straight line. The slick way to test "not collinear" without any division or floating point is the cross product.

From the first point A, build two vectors: AB = B - A and AC = C - A. Their cross product is (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1). This value is the signed area of the parallelogram they span.

If the cross product is zero, the two vectors point along the same line (or a point repeats), meaning the three points are collinear, so it is not a boomerang. If it is non-zero, they bend, and the answer is true.

Example: [[1,1],[2,3],[3,2]] gives AB = (1,2) and AC = (2,1), so the cross is 1*1 - 2*2 = -3. That is not zero, so the three points form a valid boomerang.

It works in constant time because it is just a handful of subtractions and multiplications, no loops needed.

Time: O(1) Space: O(1)