587.安装栅栏

题解

题目：计算凸包

思路：模板题凸包题，Andrew算法

代码

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))
}