Largest Triangle Area

🏠 ⬅️ ➡️

Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] Output: 2.00000 Explanation: The five points are shown in the above figure. The red triangle is the largest.

Example 2:

Input: points = [[1,0],[0,0],[0,1]] Output: 0.50000

Constraints:

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • All the given points are unique.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem:
    ! Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points.
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 50
    real(kind=DP), dimension(n) :: points
    real(kind=DP) :: area
    integer :: i, j, k

    call get_points(points)

    do i = 1, size(points)-2
        do j = i+1, size(points)-1
            do k = j+1, size(points)
                area = triangle_area(points(i), points(j), points(k))
                write (unit=error_unit, fmt='(A,F10.5)') 'Area: ', area
            end do
        end do
    end do

contains

    subroutine get_points(points)
        ! Reads the input points from stdin and stores them in the array points
        implicit none
        real(kind=DP), dimension(:), intent(out) :: points
        integer :: i, n
        character(len=100) :: line

        read (unit=input_unit, fmt='(I10)') n
        if (n > size(points)) then
            write (unit=error_unit, fmt='(A)') 'Too many points'
            stop 1
        end if

        do i = 1, n
            read (unit=input_unit, fmt='(A)') line
            read (unit=line, fmt='(2(I10,1X))') points(i), points(i+n)
        end do
    end subroutine get_points

    function triangle_area(a, b, c) result(area)
        ! Returns the area of the triangle formed by the points a, b and c
        implicit none
        real(kind=DP), value :: a(2), b(2), c(2)
        real(kind=DP) :: area

        area = abs((a(1)*b(2)+b(1)*c(2)+c(1)*a(2)-a(2)*b(1)-b(2)*c(1)-c(2)*a(1)) / 2.0D0)
    end function triangle_area

end program main
❌ Compiled
❌ Executed
❌ Correct 
module largest_triangle

implicit none

contains

real function largest_triangle(points) result(area)

! Given an array of points on the X-Y plane, return the area of the largest triangle that can be formed by any three different points.

! Input:
!   points: array of points on the X-Y plane, where points[i] = [xi, yi]
! Output:
!   area: the area of the largest triangle that can be formed by any three different points

real, intent(in) :: points(:, :)
real :: x1, y1, x2, y2, x3, y3, area

! Initialize the largest triangle area to 0
area = 0.0

! Loop through all possible combinations of three points
do i = 1, size(points, 1) - 2
    do j = i + 1, size(points, 1) - 1
        do k = j + 1, size(points, 1)

            ! Calculate the area of the current triangle
            x1 = points(i, 1)
            y1 = points(i, 2)
            x2 = points(j, 1)
            y2 = points(j, 2)
            x3 = points(k, 1)
            y3 = points(k, 2)
            area = abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0)

            ! Update the largest triangle area if necessary
            if (area > largest_triangle) then
                largest_triangle = area
            end if

        end do
    end do
end do

end function

end module

program test_largest_triangle

use largest_triangle

implicit none

! Test case 1:
! Input: [[0,0], [0,1], [1,0], [0,2], [2,0]]
! Output: 2.00000
! Explanation: The five points are shown in the above figure. The red triangle is the largest.
call assert(abs(largest_triangle([[0,0], [0,1], [1,0], [0,2], [2,0]]) - 2.0) < 1e-5)

! Test case 2:
! Input: [[1,0], [0,0], [0,1]]
! Output: 0.50000
call assert(abs(largest_triangle([[1,0], [0,0], [0,1]]) - 0.5) < 1e-5)

contains

subroutine assert(condition)

logical, intent(in) :: condition
integer :: error_code

if (.not. condition) then
    error_code = 1
else
    error_code = 0
end if

if (error_code /= 0) then
    write (*, '(A)') 'Test failed.'
else
    write (*, '(A)') 'Test passed.'
end if

end subroutine

end program
🌐 Data from online sources 
def is_shifted(s, goal):
    if len(s) != len(goal): return False

    s = s + s
    return goal in s

The algorithm first checks if the length of both input strings is not equal, in which case it returns false as they can't possibly be shifted versions of each other. If they are of the same length, it concatenates the string s with itself, which creates all possible shifted combinations of s. Then it checks whether the goal is present in this concatenated string or not. If it is present, it returns true (as s can be shifted to obtain the goal), else it returns false.

🌐 Data from online sources 
bool isShifted(string s, string goal) {
    if(s.length() != goal.length()) return false;

    s = s + s;
    return s.find(goal) != string::npos;
}

The algorithm first checks if the length of both input strings is not equal, in which case it returns false as they can't possibly be shifted versions of each other. If they are of the same length, it concatenates the string s with itself, which creates all possible shifted combinations of s. Then it checks whether the goal is present in this concatenated string or not. If it is present, it returns true (as s can be shifted to obtain the goal), else it returns false.