Problem
题目大意：给你一些点，求用这些点能够成的最大的三角形面积是多少？
https://leetcode.com/problems/largest-triangle-area/description/
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^-6of the true value will be accepted as correct.
Solution: Brute Force
Time complexity: O(n^3)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 11 ms class Solution { public: double largestTriangleArea(vector<vector<int>>& points) { const int n = points.size(); double best = 0.0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) { const double a = dist(points[i], points[j]); const double b = dist(points[i], points[k]); const double c = dist(points[j], points[k]); const double s = (a + b + c) / 2; const double area = sqrt(s * (s - a) * (s - b) * (s - c)); best = max(best, area); } return best; } private: static inline double dist(const vector<int>& p1, const vector<int>& p2) { return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1])); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment