leetcode-go/leetcode/hard/587.erect-the-fence.go

type Points []Point

func (pts Points) Len() int { return len(pts) }
func (pts Points) Less(i, j int) bool {
	if pts[i].X != pts[j].X {
		return pts[i].X < pts[j].X
	}
	return pts[i].Y < pts[j].Y
}
func (pts Points) Swap(i, j int) { pts[i], pts[j] = pts[j], pts[i] }

type none struct{}

/**
 * Definition for a point.
 * type Point struct {
 *     X int
 *     Y int
 * }
 */
func outerTrees(points []Point) []Point {
	k, n := 0, len(points)
	sort.Sort(Points(points))
	pts := make([]Point, n)
	for i := 0; i < n; i++ {
		for 1 < k { // a x b = dx1*dy2 - dx2*dy1 <= 0
			dx1, dx2 := pts[k-1].X-pts[k-2].X, points[i].X-pts[k-1].X
			dy1, dy2 := pts[k-1].Y-pts[k-2].Y, points[i].Y-pts[k-1].Y
			if dx1*dy2 <= dx2*dy1 {
				break
			}
			k--
		}
		pts[k] = points[i]
		k++
	}
	set := make(map[Point]none)
	for i := 0; i < k; i++ {
		set[pts[i]] = none{}
	}
	k = 0
	for i := n - 1; 0 <= i; i-- {
		for 1 < k { // a x b = dx1*dy2 - dx2*dy1 <= 0
			dx1, dx2 := pts[k-1].X-pts[k-2].X, points[i].X-pts[k-1].X
			dy1, dy2 := pts[k-1].Y-pts[k-2].Y, points[i].Y-pts[k-1].Y
			if dx1*dy2 <= dx2*dy1 {
				break
			}
			k--
		}
		pts[k] = points[i]
		k++
	}
	for i := 0; i < k; i++ {
		set[pts[i]] = none{}
	}
	res := make([]Point, len(set))
	k = 0
	for p, _ := range set {
		res[k] = p
		k++
	}
	return res
}