Задача: Треугольник наибольшей площади

Условие: дается массив точек на плоскости X-Y, где точки [i] = [xi, yi], верните площадь самого большого треугольника, который может быть образован любыми тремя различными точками. Будут приняты ответы в пределах 10-5 от фактического ответа.

Пример:

Ввод: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]

Вывод: 2.00000

Объяснение:

Ввод: points = [[1,0],[0,0],[0,1]]

Вывод: 0.50000

Решение: Go

Временная сложность: O(N^3)

Пространственная сложность: O(1)

func largestTriangleArea(points [][]int) float64 {

    // Heron's formula
    // triangle's lengths a, b, c
    // S = sqrt((a+b+c) * (a+b-c) * (a+c-b) * (b+c-a)) / 4
    md := make(map[int]float64)
    
    var res float64 = 0
    for i := 0; i < len(points); i++ {
        for j := i + 1; j < len(points); j++ {
            mask := (1<<i)|(1<<j)
            x := md[mask]
            if x == 0 {
                x = distance(points[i], points[j])
                md[mask] = x
            }
            for k := j + 1; k < len(points); k++ {
                mask = (1<<i)|(1<<k)
                y := md[mask]
                if y == 0 {
                    y = distance(points[i], points[k])
                    md[mask] = y
                }
                mask = (1<<j)|(1<<k)
                z := md[mask]
                if z == 0 {
                    z = distance(points[j], points[k])
                    md[mask] = z
                }
                
                if x + y < z || x + z < y || y + z < x {
                    continue
                }
                
                if v := (x+y+z)*(x+y-z)*(x+z-y)*(y+z-x); v > res {
                    res = v
                }
            }
        }
    }
    
    return math.Sqrt(res) / 4.0
}

func distance(p1 []int, p2 []int) float64 {
    x := p1[0] - p2[0]
    y := p1[1] - p2[1]
    return math.Sqrt(float64(x*x + y*y))
}