golang力扣leetcode 587.安装栅栏

func outerTrees(trees [][]int) [][]int {
  n := len(trees)
  if n < 4 {
    return trees
  }
  sort.Slice(trees, func(i, j int) bool {
    a, b := trees[i], trees[j]
    return a[0] < b[0] || a[0] == b[0] && a[1] < b[1]
  })
  hull := []int{0}
  used := make([]bool, n)
  //计算一半的凸包
  for i := 1; i < n; i++ {
    for len(hull) > 1 {
      a := trees[hull[len(hull)-2]]
      b := trees[hull[len(hull)-1]]
      c := trees[i]
      if getArea(a, b, c) < 0 {
        used[hull[len(hull)-1]] = false
        hull = hull[:len(hull)-1]
      } else {
        break
      }
    }
    used[i] = true
    hull = append(hull, i)
  }
  //计算一半的凸包
  m := len(hull)
  for i := n - 2; i >= 0; i-- {
    if !used[i] {
      for len(hull) > m {
        a := trees[hull[len(hull)-2]]
        b := trees[hull[len(hull)-1]]
        c := trees[i]
        if getArea(a, b, c) < 0 {
          used[hull[len(hull)-1]] = false
          hull = hull[:len(hull)-1]
        } else {
          break
        }
      }
      used[i] = true
      hull = append(hull, i)
    }
  }
  hull = hull[:len(hull)-1]
  ans := make([][]int, len(hull))
  for i, idx := range hull {
    ans[i] = trees[idx]
  }
  return ans
}
func subtraction(a, b []int) []int { //计算向量
  return []int{a[0] - b[0], a[1] - b[1]}
}
func cross(a, b []int) int { //向量叉积
  return a[0]*b[1] - a[1]*b[0]
}
func getArea(a, b, c []int) int { //判断是否左拐，大于0则左拐
  return cross(subtraction(b, a), subtraction(c, a))
}