2022-02-19: fence installation. In a two-dimensional garden, there are some trees represented by (x, y) coordinates. As the installation cost is very expensive, your task is to enclose all the trees w

2022-02-19： Install fence .
In a two-dimensional Garden , There are some uses. (x, y) Coordinate tree . Because the installation cost is very expensive , Your task is to surround all the trees with the shortest rope . Only when all the trees are surrounded by ropes , A garden can fence . You need to find the coordinates of the trees right on the fence boundary .
Power button 587.

answer 2022-02-19：

convex hull . Two dimensional coordinate system , From left to right , Sort from bottom to top .

The code to use golang To write . The code is as follows ：

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 In front of the small row ,x Same ,y In front of the small row 
    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++
    }
    //  Go back to 
    //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++ {
    
        //  If i spot ,x and y, And i-1 spot ,x and y Are all the same 
        // i Point and i-1 spot , In the same place , here ,i Point not reserved 
        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)
}

//  The realization of cross multiplication 
//  Suppose there is a、b、c Three points , And give the... Of each point (x,y) Location 
//  from a To c Vector , In from a To b Which side of the vector of ？
//  If a To c Vector , In from a To b To the right of the vector , Return positive number 
//  If a To c Vector , In from a To b To the left of the vector , Return negative 
//  If a To c Vector , And from the a To b The vectors of coincide , return 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])
}

The results are as follows ：

---

Zuo Shen java Code