587.安装栅栏.md

587.安装栅栏

/*
 * @lc app=leetcode.cn id=587 lang=typescript
 *
 * [587] 安装栅栏
 */

// @lc code=start
function outerTrees(trees: [number, number][]): number[][] {}
// @lc code=end

解法 1: 通过角度找最外边的点

先找到一条边界上的边,选择其中一个点 a,然后找到枚举其他点,找到其中能跟 a 连接并跟这条边组成最大角度的点 b,则选择点 b 作为下一个判断点,直到最后找到点是已选择的点.

在实际代码中,先选择最左下角的点 [x,y],其肯定是在边界,然后虚构一个点 [x,y+1],连接这两点形成一个虚构的边,按照上面的思路去找到剩余的点,直到最后找到 [x,y] 也就找到了所有边界上的点.

这个题目需要所有在边界上的点,所以需要用一个数组去存所有角度相同的点.其中距离当前点最远的那个作为下个判断点,可以用一个变量去存,或者可以像我下面代码中将最远距离的点放在数组最后,其他都插到前面,这样做会损失一点时间复杂度,如果数据量较大就需要用变量去存.

另外关于角度的比较,代码中使用的 acos 计算的结果的单位是弧度,结果是一个实数,存在精度问题,所以比较时,通过相减是否小于1e-6来判断是否相等.

function outerTrees(trees: [number, number][]): number[][] {
  let p1: [number, number] = [Infinity, Infinity]

  for (let [x, y] of trees) {
    if (p1[0] === x && p1[1] < y) {
      p1 = [x, y]
    }

    if (p1[0] > x) {
      p1 = [x, y]
    }
  }

  const res: [number, number][] = [[p1[0], p1[1] + 1], p1]
  function getAngle(a: [number, number], b: [number, number], c: [number, number]) {
    var AB = Math.sqrt(Math.pow(b[0] - a[0], 2) + Math.pow(b[1] - a[1], 2))
    var BC = Math.sqrt(Math.pow(b[0] - c[0], 2) + Math.pow(b[1] - c[1], 2))
    var AC = Math.sqrt(Math.pow(c[0] - a[0], 2) + Math.pow(c[1] - a[1], 2))
    return Math.acos((BC * BC + AB * AB - AC * AC) / (2 * BC * AB))
  }

  while (true) {
    const last = res[res.length - 1]
    let max = 0,
      ans: [number, number][] = []
    for (let [x, y] of trees) {
      const tmp = getAngle(res[res.length - 2], res[res.length - 1], [x, y])

      if (Math.abs(tmp - max) <= 10 ** -6) {
        if (
          ans.length === 0 ||
          (x - last[0]) ** 2 + (y - last[1]) ** 2 >
            (ans[ans.length - 1][0] - last[0]) ** 2 + (ans[ans.length - 1][1] - last[1]) ** 2
        )
          ans.push([x, y])
        else ans.unshift([x, y])
      }
      if (tmp - max > 10 ** -6) {
        max = tmp
        ans = [[x, y]]
      }
    }
    if (ans.length === 0) {
      break
    }

    for (let [x, y] of ans) {
      res.push([x, y])
    }
    if (ans.length > 0 && ans[ans.length - 1][0] === p1[0] && ans[ans.length - 1][1] === p1[1]) {
      break
    }
  }
  const set = new Set<string>()

  return res.slice(1).filter(([x, y]) => {
    const str = `${x},${y}`
    if (set.has(str)) return false
    set.add(str)
    return true
  })
}