Jarvis 凸包算法 + 向量叉积：求解《812. 最大三角形面积》

var largestTriangleArea = function(points) {
  points = outTree(points)
  const n = points.length
  let ans = 0
  for (let i = 0; i < n; i++) {
    for (let j = i + 1, k = i + 2; j + 1 < n; j++) {
      while (k + 1 < n) {
        const cur = 0.5 * Math.abs(cross(points[i], points[j], points[k]))
        const next = 0.5 * Math.abs(cross(points[i], points[j], points[k + 1]))
        if (cur >= next) break
        k++
      }
      const cur = 0.5 * Math.abs(cross(points[i], points[j], points[k]))
      ans = Math.max(ans, cur)
    }
  }
  return ans
};
const outTree = points => {
  points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])
  const n = points.length, visited = new Uint8Array(n), ans = []
  let p = leftMin = 0
  do {
    q = (p + 1) % n
    for (let r = 0; r < n; r++) {
      if (r === p || r === q) continue
      if (cross(points[p], points[q], points[r]) < 0) q = r
    }
    for (let i = 0; i < n; i++) {
      if (visited[i] === 1 || i === p || i === q) continue
      if (cross(points[p], points[q], points[i]) === 0) {
        ans.push(points[i])
        visited[i] = 1
      }
    }
    if (visited[q] === 0) {
      ans.push(points[q])
      visited[q] = 1
    }
    p = q
  } while (p != leftMin)
  return ans
}
const cross = ([x1, y1], [x2, y2], [x3, y3]) => (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)

func largestTriangleArea(points [][]int) float64 {
  var ans float64
  points = outTree(points)
  n := len(points)
  for i := 0; i < n; i++ {
    for j := i + 1; j + 1 < n; j++ {
      k := j + 1
      for k + 1 < n {
        cur := trigleArea(points[i], points[j], points[k])
        next := trigleArea(points[i], points[j], points[k + 1])
        if cur >= next {
          break
        }
        k++
      }
      cur := trigleArea(points[i], points[j], points[k])
      if cur > ans {
        ans = cur
      }
    }
  }
  return ans
}
func outTree (points [][]int) [][]int {
  var ans [][]int
  n := len(points)
  visited := make([]uint, n)
  sort.SliceStable(points, func(i, j int) bool {
    if points[i][0] == points[j][0] {
      return points[i][1] > points[j][1]
    }
    return points[i][0] > points[j][0]
  })
  p, leftMin := 0, 0
  for true {
    q := (p + 1) % n
    for r := 0; r < n; r++ {
      if r == p || r == q {
        continue
      }
      if cross(points[p], points[q], points[r]) < 0 {
        q = r
      }
    }
    for i := 0; i < n; i++ {
      if visited[i] == 1 || i == p || i == q {
        continue
      }
      if cross(points[p], points[q], points[i]) == 0 {
        ans = append(ans, points[i])
        visited[i] = 1
      }
    }
    if visited[q] == 0 {
      ans = append(ans, points[q])
      visited[q] = 1
    }
    p = q
    if p == leftMin {
      break
    }
  }
  return ans
}
func cross (p []int, q []int, r []int) int {
  x1, y1, x2, y2, x3, y3 := p[0], p[1], q[0], q[1], r[0], r[1]
  return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) 
}
func trigleArea (p []int, q []int, r []int) float64 {
  return math.Abs(float64(cross(p, q, r))) * 0.5
}

function largestTriangleArea(points: number[][]): number {
  points = outTree(points)
  const n = points.length
  let ans = 0
  for (let i = 0; i < n; i++) {
    for (let j = i + 1, k = i + 2; j + 1 < n; j++) {
      while (k + 1 < n) {
        const cur = 0.5 * Math.abs(cross(points[i], points[j], points[k]))
        const next = 0.5 * Math.abs(cross(points[i], points[j], points[k + 1]))
        if (cur >= next) break
        k++
      }
      const cur = 0.5 * Math.abs(cross(points[i], points[j], points[k]))
      ans = Math.max(ans, cur)
    }
  }
  return ans
};
const outTree = (points: number[][]): number[][] => {
  points.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0])
  const n = points.length, visited = new Uint8Array(n), ans = []
  let p = 0, leftMin = 0
  do {
    let q = (p + 1) % n
    for (let r = 0; r < n; r++) {
      if (r === p || r === q) continue
      if (cross(points[p], points[q], points[r]) < 0) q = r
    }
    for (let i = 0; i < n; i++) {
      if (visited[i] === 1 || i === p || i === q) continue
      if (cross(points[p], points[q], points[i]) === 0) {
        ans.push(points[i])
        visited[i] = 1
      }
    }
    if (visited[q] === 0) {
      ans.push(points[q])
      visited[q] = 1
    }
    p = q
  } while (p != leftMin)
  return ans
}
const cross = ([x1, y1]: number[], [x2, y2]: number[], [x3, y3]: number[]) => (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)

class Solution {
  function largestTriangleArea($points) {
    $points = $this->outTree($points);
    $n = count($points);
    $r = 0;
    for ($i = 0; $i < $n; $i++) {
      for ($j = $i + 1, $k = $i + 2; $j + 1 < $n; $j++) {
        while ($k + 1 < $n) {
          $cur = $this->trigleArea($points[$i], $points[$j], $points[$k]);
          $next = $this->trigleArea($points[$i], $points[$j], $points[$k + 1]);
          if ($cur >= $next) break;
          $k++;
        }
        $cur = $this->trigleArea($points[$i], $points[$j], $points[$k]);
        $r = max($r, $cur);
      }
    }
    return $r;
  }
  function outTree($points) {
    $n = count($points);
    $visited = array_fill(0, $n, 0);
    $ans = [];
    usort($points, function($a, $b) {
      if ($a[0] === $b[0]) return $a[1] > $b[1];
      return $a[0] > $b[0];
    });
    $p = $leftMin = 0;
    do {
      $q = ($p + 1) % $n;
      for ($r = 0; $r < $n; $r++) {
        if ($r === $p || $r === $q) continue;
        if ($this->cross($points[$p], $points[$q], $points[$r]) < 0) $q = $r;
      }
      for ($i = 0; $i < $n; $i++) {
        if ($visited[$i] === 1 || $i === $p || $i === $q) continue;
        if ($this->cross($points[$p], $points[$q], $points[$i]) === 0) {
          $visited[$i] = 1;
          $ans []= $points[$i];
        }
      }
      if ($visited[$q] === 0) {
        $visited[$q] = 1;
        $ans []= $points[$q];
      }
      $p = $q;
    } while ($p != $leftMin);
    return $ans;
  }
  function cross($p, $q, $r) {
    list($x1, $y1) = $p;
    list($x2, $y2) = $q;
    list($x3, $y3) = $r;
    return ($x2 - $x1) * ($y3 - $y1) - ($x3 - $x1) * ($y2 - $y1);
  }
  function trigleArea($p, $q, $r) {
    return abs($this->cross($p, $q, $r)) * .5;
  }
}