Largest Triangle Area, by LeetCode
Straightforward problem by LeetCode, here it is https://leetcode.com/problems/largest-triangle-area/description/:
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;
}
}
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;
}
}
haha, it's been a while since I had so many nested loops )
ReplyDeleteclass 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;
}
};