LeetCode - Algorithms - 1037. Valid Boomerang

It’s easy indeed once you think about the slope of a line.

Zoomerang a Boomerang

by Ruth I. Dowell

Zoomerang a boomerang
Around a maple tree!
Zoomrang a boomerang
But don’t hit me!

from Poems to make your belly laugh

Problem

1037. Valid Boomerang

A boomerang is a set of 3 points that are all distinct and not in a straight line.

Java

cross product

1
2
3
4
5
class Solution {
    public boolean isBoomerang(int[][] points) {
        return (points[2][1]-points[0][1])*(points[1][0]-points[0][0]) == (points[1][1]-points[0][1])*(points[2][0]-points[0][0])?false:true;      
    }
}

Submission Detail

  • 190 / 190 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Boomerang.
  • Memory Usage: 37.2 MB, less than 100.00% of Java online submissions for Valid Boomerang.

Heron’s formula

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isBoomerang(int[][] points) {
		double a = Math.sqrt(Math.pow(points[1][0] - points[0][0], 2) + Math.pow(points[1][1] - points[0][1], 2));
		double b = Math.sqrt(Math.pow(points[2][0] - points[1][0], 2) + Math.pow(points[2][1] - points[1][1], 2));
		double c = Math.sqrt(Math.pow(points[2][0] - points[0][0], 2) + Math.pow(points[2][1] - points[0][1], 2));
		double s = (a + b + c) / 2;
		double A = Math.sqrt(s * (s - a) * (s - b) * (s - c));
		return A != 0;
    }
}

Submission Detail

  • 190 / 190 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Boomerang.
  • Memory Usage: 36.9 MB, less than 83.23% of Java online submissions for Valid Boomerang.

Gauss’s area formula

Shoelace formula

let \( \mathbf {A} \) be the area of the triangle whose vertices are given by the coordinates \( (x_{1},y_{1}) \), \( (x_{2},y_{2}) \), and \( (x_{3},y_{3}) \).

\( \mathbf {A} \) can be written as a determinant

\( {\displaystyle \mathbf
{A} ={\frac {1}{2}}
{
\begin{vmatrix}1&1&1 \\
x_{1}&x_{2}&x_{3} \\
y_{1}&y_{2}&y_{3}
\end{vmatrix}
}
}
\)

If the coordinates are written in a clockwise order, the value of the determinant will be \( {\displaystyle -\mathbf {A} } \)

Rearranging another way

\( {\displaystyle \mathbf {A} ={\frac {1}{2}}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3}|} \)

which is the form of the shoelace formula. This formula can be extended to find the area of any polygon since a simple polygon can be divided into triangles.

1
2
3
4
5
6
7
class Solution {
    public boolean isBoomerang(int[][] points) {
		int A = points[0][0] * points[1][1] + points[1][0] * points[2][1] + points[2][0] * points[0][1]
				- points[1][0] * points[0][1] - points[2][0] * points[1][1] - points[0][0] * points[2][1];
		return A != 0;
    }
}

Submission Detail

  • 190 / 190 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Valid Boomerang.
  • Memory Usage: 37.7 MB, less than 15.65% of Java online submissions for Valid Boomerang.