2022-02-19：安装栅栏。 在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。

2022-02-19：安装栅栏。
在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。
力扣587。

答案2022-02-19：

凸包。二维坐标系，从左往右，从下往上排序。

代码用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])

}

执行结果如下：

左神java代码

2022-02-19：安装栅栏。 在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。的相关教程结束。