题目链接

安装栅栏

题目描述

image.png

解题思路

方法一: Jarvis 算法

image.png
这里需要注意：r是在向量pq的左边，而不是上下边的概念image.png
image.png
实现代码：

  1. class Solution {
  2.     public int[][] outerTrees(int[][] trees) {
  3.         int n = trees.length;
  4.         if (n < 4) {
  5.             return trees;
  6.         }
  7.         int leftMost = 0;
  8.         for (int i = 0; i < n; i++) {
  9.             if (trees[i][0] < trees[leftMost][0]) {
  10.                 leftMost = i;
  11.             }
  12.         }
  14.         List<int[]> res = new ArrayList<int[]>();
  15.         boolean[] visit = new boolean[n];
  16.         int p = leftMost;
  17.         do {
  18.             int q = (p + 1) % n;
  19.             for (int r = 0; r < n; r++) {
  20.                 /* 如果 r 在 pq 的右侧，则 q = r */ 
  21.                 if (cross(trees[p], trees[q], trees[r]) < 0) {
  22.                     q = r;
  23.                 }
  24.             }
  25.             /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
  26.             for (int i = 0; i < n; i++) {
  27.                 if (visit[i] || i == p || i == q) {
  28.                     continue;
  29.                 }
  30.                 if (cross(trees[p], trees[q], trees[i]) == 0) {
  31.                     res.add(trees[i]);
  32.                     visit[i] = true;
  33.                 }
  34.             }
  35.             if  (!visit[q]) {
  36.                 res.add(trees[q]);
  37.                 visit[q] = true;
  38.             }
  39.             p = q;
  40.         } while (p != leftMost);
  41.         return res.toArray(new int[][]{});
  42.     }
  44.     public int cross(int[] p, int[] q, int[] r) {
  45.         return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
  46.     }
  47. }