269. Biggest Triangle
A drone operator has marked points on a map, each given as [x, y] with integer coordinates. She wants to fly around the largest possible triangular patrol zone whose three corners are chosen from the marked points; the points may repeat or lie on one straight line.
Return the maximum area of a triangle formed by any three of the points, as a double. Triples that are collinear or contain a repeated point have area 0, so the answer is 0.0 when no proper triangle exists. Answers within 1e-6 of the true value are accepted. With at most 50 points, checking every triple using the cross product takes O(n^3) time and O(1) extra space.
Example 1
- Input:
- points = [[0,0],[7,1],[2,6],[-4,3]]
- Output:
- 22.5
- Explanation:
The triangle (7,1), (2,6), (-4,3) has the largest area, 22.5.
Example 2
- Input:
- points = [[1,1],[2,2],[5,5]]
- Output:
- 0
- Explanation:
All three points lie on the line y = x, so no area is enclosed.
Constraints
3 ≤ points.length ≤ 50
points[i].length = 2
-70 ≤ x, y ≤ 70
Points are not necessarily distinct.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001
Expected complexity
- Time
- O(n^3)
- Space
- O(1)