812. Largest Triangle Area

发表于 | 分类于 | |

812. Largest Triangle Area

题目描述

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation:
The five points are show in the figure below. The red triangle is the largest.

Notes:

  • 3 <= points.length <= 50.
  • No points will be duplicated.
  • -50 <= points[i][j] <= 50.
  • Answers within 10^-6 of the true value will be accepted as correct.

题目大意

给定一组坐标，求围成的三角形的最大面积。

解题思路

暴力搜索，最主要是要知道根据 Shoelace formula 求三角形面积。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func largestTriangleArea(_ points: [[Int]]) -> Double {
        func triangleArea(p1: [Int], p2: [Int], p3: [Int]) -> Double {
            return 0.5 * abs(Double(p1[0] * (p2[1] - p3[1])
                + p2[0] * (p3[1] - p1[1])
                + p3[0] * (p1[1] - p2[1])))
        }
        var ans = 0.0
        for i in 0..<points.count {
            for j in i+1..<points.count {
                for k in j+1..<points.count {
                   ans = max(ans, triangleArea(p1: points[i], p2: points[j], p3: points[k]))
                }
            }
        }
        return ans
    }
}
0%