diff options
author | Jack Sangdahl <[email protected]> | 2025-09-26 21:08:43 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-26 21:08:43 -0600 |
commit | 48f4961febc7d03056cd826682e4b3277c7b20ca (patch) | |
tree | c7b42172d3db06468f818923bd388dbc94a97168 | |
parent | 23353c144ac9b158af7616dc46b636d53b73ce34 (diff) | |
download | leetcode-48f4961febc7d03056cd826682e4b3277c7b20ca.tar.gz leetcode-48f4961febc7d03056cd826682e4b3277c7b20ca.zip |
812. largest triangle area
-rw-r--r-- | largest_triangle_area.c | 37 | ||||
-rw-r--r-- | largest_triangle_area.py | 34 |
2 files changed, 71 insertions, 0 deletions
diff --git a/largest_triangle_area.c b/largest_triangle_area.c new file mode 100644 index 0000000..381c200 --- /dev/null +++ b/largest_triangle_area.c @@ -0,0 +1,37 @@ +// 812. Largest Triangle Area +#include "leetcode.h" + +/* + * given an array of points on the x-y plane 'points' where 'points[i] = [x_i, + * y_i]' return the area of the largest triangle that can be formed by any three + * different points. answers within 10^-5 will be accepted. + */ + +double largestTriangleArea(int **points, int pointsSize, int *pointsColSize) { + double ans = INT_MIN; + for (int i = 0; i < pointsSize; i++) + for (int j = i + 1; j < pointsSize; j++) + for (int k = j + 1; k < pointsSize; k++) { + int x1 = points[i][0], y1 = points[i][1]; + int x2 = points[j][0], y2 = points[j][1]; + int x3 = points[k][0], y3 = points[k][1]; + double tmp = abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))); + ans = fmax(ans, 0.5 * tmp); + } + return ans; +} + +int main() { + int p1i[5][2] = {{0, 0}, {0, 1}, {1, 0}, {0, 2}, {2, 0}}, + p2i[3][2] = {{1, 0}, {0, 0}, {0, 1}}; + struct two_d_arr *p1 = + two_d_arr_init(ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i); + struct two_d_arr *p2 = + two_d_arr_init(ARRAY_SIZE(p2i), ARRAY_SIZE(p2i[0]), p2i); + printf("%f\n", largestTriangleArea(p1->arr, p1->row_size, + p1->col_size)); // expect: 2.00000 + printf("%f\n", largestTriangleArea(p2->arr, p2->row_size, + p2->col_size)); // expect: 0.50000 + two_d_arr_free(p1); + two_d_arr_free(p2); +} diff --git a/largest_triangle_area.py b/largest_triangle_area.py new file mode 100644 index 0000000..506586f --- /dev/null +++ b/largest_triangle_area.py @@ -0,0 +1,34 @@ +# 812. Largest Triangle Area +from itertools import combinations + +""" +given an array of points on the x-y plane 'points' where 'points[i] = [x_i, +y_i]' return the area of the largest triangle that can be formed by any three +different points. answers within 10^-5 will be accepted. +""" + + +class Solution(object): + def largestTriangleArea(self, points): + """ + :type points: List[List[int]] + :rtype: float + """ + return max( + 0.5 + * abs( + i[0] * j[1] + + j[0] * k[1] + + k[0] * i[1] + - j[0] * i[1] + - k[0] * j[1] + - i[0] * k[1] + ) + for i, j, k in combinations(points, 3) + ) + + +if __name__ == "__main__": + obj = Solution() + print(obj.largestTriangleArea(points=[[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]])) + print(obj.largestTriangleArea(points=[[1, 0], [0, 0], [0, 1]])) |