安装栅栏。
在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
力扣587。
凸包。二维坐标系，从左往右，从下往上排序。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
)
func main() {
points := [][]int{{1, 1}, {2, 2}, {2, 0}, {2, 4}, {3, 3}, {4, 2}}
ret := outerTrees(points)
fmt.Println(ret)
}
func outerTrees(points [][]int) [][]int {
n := len(points)
s := 0
stack := make([][]int, n<<1)
// x小的排前面，x一样的，y小的排前面
sort.Slice(points, func(i, j int) bool {
a := points[i]
b := points[j]
if a[0] != b[0] {
return a[0] < b[0]
} else {
return a[1] < b[1]
}
})
for i := 0; i < n; i++ {
for s > 1 && cross(stack[s-2], stack[s-1], points[i]) > 0 {
s--
}
stack[s] = points[i]
s++
}
for i := n - 2; i >= 0; i-- {
for s > 1 && cross(stack[s-2], stack[s-1], points[i]) > 0 {
s--
}
stack[s] = points[i]
s++
}
// 去重返回
//Arrays.sort(stack, 0, s, (a, b) -> b[0] == a[0] ? b[1] - a[1] : b[0] - a[0]);
n = 1
for i := 1; i < s; i++ {
// 如果i点，x和y，与i-1点，x和y都一样
// i点与i-1点，在同一个位置，此时，i点不保留
if stack[i][0] != stack[i-1][0] || stack[i][1] != stack[i-1][1] {
stack[n] = stack[i]
n++
}
}
return stack[0:n]
//return Arrays.copyOf(stack, n)
}
// 叉乘的实现
// 假设有a、b、c三个点，并且给出每个点的(x,y)位置
// 从a到c的向量，在从a到b的向量的哪一侧？
// 如果a到c的向量，在从a到b的向量右侧，返回正数
// 如果a到c的向量，在从a到b的向量左侧，返回负数
// 如果a到c的向量，和从a到b的向量重合，返回0
func cross(a, b, c []int) int {
return (b[1]-a[1])*(c[0]-b[0]) - (b[0]-a[0])*(c[1]-b[1])
}执行结果如下：
