Largest Triangle Area, by LeetCode

Straightforward problem by LeetCode, here it is 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.
Given the low range of the input points (max = 50), an N^3 solution should do it here. The key is to find the formula of the area of the triangle given the three coordinates, it can be found here: http://www.mathopenref.com/coordtrianglearea.html. Code is below, many cheers! Marcelo

public class Solution
{
public double LargestTriangleArea(int[][] points)
{
double largest = -1;
for (int i = 0; i < points.Length; i++)
{
for (int j = i + 1; j < points.Length; j++)
{
for (int z = j + 1; z < points.Length; z++)
{
double Ax = points[i][0];
double Ay = points[i][1];
double Bx = points[j][0];
double By = points[j][1];
double Cx = points[z][0];
double Cy = points[z][1];

double area = (Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By)) / 2;
if (area < 0) area = -area;
if (area > largest) largest = area;
}
}
}

return largest;
}
}

Comments

  1. haha, it's been a while since I had so many nested loops )

    class Solution {
    public:
    double largestTriangleArea(vector>& points) {
    double largest_area = 0;
    for (int i = 0; i < points.size(); ++i) {
    const auto& point1 = points[i];
    for (int j = i+1; j < points.size(); ++j) {
    const auto& point2 = points[j];
    for (int k = j + 1; k < points.size(); ++k) {
    const auto& point3 = points[k];
    largest_area = max(largest_area,
    abs(static_cast(point1[0] * (point2[1] - point3[1]) +
    point2[0] * (point3[1] - point1[1]) +
    point3[0] * (point1[1] - point2[1])
    )));
    }
    }
    }
    return largest_area / 2;
    }
    };

    ReplyDelete

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

Golang vs. C#: performance characteristics (simple case study)

Advent of Code - Day 7, 2024: Backtracking and Eval