题目描述（leetcode-587）

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

example-1

注意:

  • 所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
  • 输入的整数在 0 到 100 之间。
  • 花园至少有一棵树。
  • 所有树的坐标都是不同的。
  • 输入的点没有顺序。输出顺序也没有要求

暴力解法

凸包一定是最外围的那些点圈成，所以假设有n个点，那么最多可以构造出n(n−1)/2
条边，算法如下：

  1. 选定一条边，遍历其他n-2个点，如果所有点都在该条边的一侧，则加入凸包集合。
  2. 不断重复步骤1，直到所有边都被遍历过。

显然，时间复杂度为O(n3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public List<Point> outerTrees(Point[] points) {
    Set<Point> result = new HashSet<>();
    if (points.length == 1) {
        result.add(points[0]);
        return new ArrayList<>(result);
    }

    for (int i = 0; i < points.length; i++) {
        for (int j = i + 1; j < points.length; j++) {
            int oneSide = 0, anotherSide = 0;
            for (int k = 0; k < points.length; k++) {
                if (k == i || k == j) continue;
                if (pointPosition(points[i], points[j], points[k]) > 0) {
                    oneSide++;
                } else if (pointPosition(points[i], points[j], points[k]) < 0) {
                    anotherSide++;
                }
            }
            if (oneSide == points.length - 2 || oneSide == 0) {
                result.add(points[i]);
                result.add(points[j]);
            }
            if (anotherSide == points.length - 2 || anotherSide == 0) {
                result.add(points[i]);
                result.add(points[j]);
            }
        }
    }
    return new ArrayList<>(result);
}

其中pointPosition用于判断点temp在直线p1p2的哪一侧，当返回结果为正时，temp在直线p1p2的左侧；当结果为负时，temp在直线p1p2的右边。

1
2
3
private int pointPosition(Point p1, Point p2, Point temp) {
    return p1.x * p2.y + temp.x * p1.y + p2.x * temp.y - temp.x * p2.y - p2.x * p1.y - p1.x * temp.y;
}

分治法

在一个凸包中，横坐标最小和横坐标最大的点一定是凸包上的边界点。根据此性质，可以得到分治解法

算法步骤如下：

  1. 选取横坐标最小和最大的两个点P1和Pn，这两个点一定是凸包上的点。直线P1Pn把点集分成了两部分，即上面和下面两部分，分别叫做上凸包和下凸包。
  2. 对上凸包：求距离直线P1Pn最远的点Pmax
  3. 作直线P1Pmax、PnPmax，把直线 P1Pmax 左侧的点当成是上包，把直线 PnPmax 右侧的点也当成是上包。
  4. 重复步骤2、3。
  5. 对下凸包也作同样的操作

example-2

1
2
3
4
5
6
7
8
Set<Point> result = new HashSet<>();

public List<Point> outerTrees(Point[] points) {
    List<Point> part = Arrays.asList(points);
    subOuterTrees(part, true);
    subOuterTrees(part, false);
    return new ArrayList<>(result);
}

对子问题的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
private void subOuterTrees(List<Point> points, boolean isUpConvex) {

    if (points.size() == 0) return;

    Collections.sort(points, new Comparator<Point>() {
        // 按横坐标降序排列，若相同，比较纵坐标
        public int compare(Point p1, Point p2) {
            return p1.x != p2.x ? (p1.x - p2.x) : (p1.y - p2.y);
        }
    });

    // 分别记录横坐表最小和最大的点
    int firstIndex = 0;
    int lastIndex = points.size() - 1;
    result.add(points.get(firstIndex));
    result.add(points.get(lastIndex));

    if (points.size() == 2) return;s

    // 判断是否在线上
    boolean inLine = true;

    for (int i = 0; i < points.size(); i++) {
        if (i == firstIndex || i == lastIndex) continue;
        if (pointPosition(points.get(firstIndex), points.get(lastIndex), points.get(i)) != 0) {
            inLine = false;
            break;
        }
    }

     // 遍历完之后若全部在同一直线
     if (inLine) {
        result.addAll(points);
        return;
    }

    // 记录距离线最远的点
    int maxIndex = -1;
    // 记录最远距离
    int max = 0;

    for (int i = 0; i < points.size(); i++) {
        if (i == firstIndex || i == lastIndex)
            continue;

        // 上凸包
        if (isUpConvex && pointPosition(points.get(firstIndex)points.get(lastIndex), points.get(i)) > max) {
            maxIndex = i;
            max = pointPosition(points.get(firstIndex), points.get(lastIndex), points.get(i));
        }

        // 下凸包
        if (!isUpConvex && -pointPosition(points.get(firstIndex points.get(lastIndex), points.get(i)) > max) {
            maxIndex = i;
            max = -pointPosition(points.get(firstIndex), points.get(lastIndex), points.get(i));
        }
    }

    if (maxIndex == -1) return;

    List<Point> pointsSet1 = new ArrayList<>();
    split(firstIndex, maxIndex, points, pointsSet1, isUpConvex);
    subOuterTrees(pointsSet1, isUpConvex);

    List<Point> pointsSet2 = new ArrayList<>();
    split(lastIndex, maxIndex, points, pointsSet2, !isUpConvex);
    subOuterTrees(pointsSet2, isUpConvex);
}

子集的划分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void split(int index1, int index2, List<Point> points, List<Point> part, boolean isUpConvex) {
    for (int i = 0; i < points.size(); i++) {
        if (i == index1 || i == index2) {
            part.add(points.get(i));
        }
            
        if (isUpConvex && pointPosition(points.get(index1), points.get(index2), points.get(i)) >= 0) {
            part.add(points.get(i));
        }
        if (!isUpConvex && pointPosition(points.get(index1), points.get(index2), points.get(i)) <= 0) {
            part.add(points.get(i));
        }
    }
}