{"id":2446,"date":"2018-04-08T00:10:57","date_gmt":"2018-04-08T07:10:57","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2446"},"modified":"2018-04-17T23:35:24","modified_gmt":"2018-04-18T06:35:24","slug":"leetcode-812-largest-triangle-area","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-812-largest-triangle-area\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 812. Largest Triangle Area"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u70b9\uff0c\u6c42\u7528\u8fd9\u4e9b\u70b9\u80fd\u591f\u6210\u7684\u6700\u5927\u7684\u4e09\u89d2\u5f62\u9762\u79ef\u662f\u591a\u5c11\uff1f<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/largest-triangle-area\/description\/\">https:\/\/leetcode.com\/problems\/largest-triangle-area\/description\/<\/a><\/p>\n<p>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.<\/p>\n<pre class=\"crayon:false\"><strong>Example:<\/strong>\r\n<strong>Input:<\/strong> points = [[0,0],[0,1],[1,0],[0,2],[2,0]]\r\n<strong>Output:<\/strong> 2\r\n<strong>Explanation:<\/strong> \r\nThe five points are show in the figure below. The red triangle is the largest.\r\n<\/pre>\n<p><img decoding=\"async\" src=\"https:\/\/s3-lc-upload.s3.amazonaws.com\/uploads\/2018\/04\/04\/1027.png\" alt=\"\" \/><\/p>\n<p><strong>Notes:<\/strong><\/p>\n<ul>\n<li><code>3 &lt;= points.length &lt;= 50<\/code>.<\/li>\n<li>No points will be duplicated.<\/li>\n<li>\u00a0<code>-50 &lt;= points[i][j] &lt;= 50<\/code>.<\/li>\n<li>Answers within\u00a0<code>10^-6<\/code>\u00a0of the true value will be accepted as correct.<\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\"\n     style=\"display:block; text-align:center;\"\n     data-ad-layout=\"in-article\"\n     data-ad-format=\"fluid\"\n     data-ad-client=\"ca-pub-2404451723245401\"\n     data-ad-slot=\"7983117522\"><\/ins><\/p>\n<h1><strong>Solution: Brute Force<\/strong><\/h1>\n<p>Time complexity: O(n^3)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 11 ms\r\nclass Solution {\r\npublic:\r\n  double largestTriangleArea(vector&lt;vector&lt;int&gt;&gt;&amp; points) {\r\n    const int n = points.size();\r\n    double best = 0.0;\r\n    for (int i = 0; i &lt; n; ++i)\r\n      for (int j = i + 1; j &lt; n; ++j)\r\n        for (int k = j + 1; k &lt; n; ++k) {          \r\n          const double a = dist(points[i], points[j]);\r\n          const double b = dist(points[i], points[k]);\r\n          const double c = dist(points[j], points[k]);\r\n          const double s = (a + b + c) \/ 2;\r\n          const double area = sqrt(s * (s - a) * (s - b) * (s - c));          \r\n          best = max(best, area);\r\n        }\r\n    return best;\r\n  }\r\nprivate:\r\n  static inline double dist(const vector&lt;int&gt;&amp; p1, const vector&lt;int&gt;&amp; p2) {\r\n    return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e9b\u70b9\uff0c\u6c42\u7528\u8fd9\u4e9b\u70b9\u80fd\u591f\u6210\u7684\u6700\u5927\u7684\u4e09\u89d2\u5f62\u9762\u79ef\u662f\u591a\u5c11\uff1f 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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127,49],"tags":[178,222,284,31,293],"class_list":["post-2446","post","type-post","status-publish","format-standard","hentry","category-geometry","category-math","tag-area","tag-easy","tag-geometry","tag-math","tag-triangle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2446","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2446"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2446\/revisions"}],"predecessor-version":[{"id":2531,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2446\/revisions\/2531"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2446"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2446"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2446"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}