587 Erect the Fence

587. Erect the Fence

1. Question

There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.

Example 1:

Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]

Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]

Explanation:

Example 2:

Input: [[1,2],[2,2],[4,2]]

Output: [[1,2],[2,2],[4,2]]

Explanation:

Even you only have trees in a line, you need to use rope to enclose them.

Note:

1. All trees should be enclosed together. You cannot cut the rope to enclose trees that will separate them in more than one group.

2. All input integers will range from 0 to 100.

3. The garden has at least one tree.

4. All coordinates are distinct.

5. Input points have NO order. No order required for output.

2. Implementation

(1) Gift Wrapping Algorithm (Jarvis's March)

思路: 视频解析

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public List<Point> outerTrees(Point[] points) {
        if (points.length < 3) {
            return Arrays.asList(points);
        }

        Point startPoint = points[0];
        int startIndex = 0;

        // Find the leftmost point as the start point
        for (int i = 1; i < points.length; i++) {
            if (points[i].x < startPoint.x) {
                startPoint = points[i];
                startIndex = i;
            }
        }

        // Use Set because Gift Wrapping Algorithm may try to insert dupilcate value
        Set<Point> res = new HashSet();
        List<Point> collinearPoints = new ArrayList();

        res.add(startPoint);

        Point curPoint = startPoint;
        int curIndex = startIndex;

        while (true) {
            Point nextPoint = points[0];
            int nextIndex = 0;

            for (int i = 1; i < points.length; i++) {
                if (curIndex == i) continue;

                int crossProduct = getCrossProduct(curPoint, nextPoint, points[i]);
                // if crossProduct > 0, points[i] is on the left of line curPoint-nextPoint
                if (crossProduct > 0) {
                    nextPoint = points[i];
                    nextIndex = i;
                    // Clear collinearPoints because we change the nextPoint
                    collinearPoints.clear();
                }
                // if crossProduct = 0, points[i] is collinear with curPoint and nextPoint
                else if (crossProduct == 0) {
                    // Update nextPoint with points[i] is points[i] is further from curPoint
                    if (getDistance(curPoint, points[i]) > getDistance(curPoint, nextPoint)) {
                        collinearPoints.add(nextPoint);
                        nextPoint = points[i];
                        nextIndex = i;
                    }
                    // If nextPoint is on the boundary of convex hull
                    // then all points in collinear points will be also on boundary.
                    else {
                        collinearPoints.add(points[i]);
                    }
                }
            }

            for (Point point : collinearPoints) {
                res.add(point);
            }

            // If nextPoint is the same as startPoint, we have formed an envelope and it is done.
            if (nextPoint == startPoint) {
                break;
            }

            // Add nextPoint to the result and set curPoint as nextPoint
            res.add(nextPoint);
            curPoint = nextPoint;
            curIndex = nextIndex;
        }

        return new ArrayList<>(res);
    }

    public int getCrossProduct(Point A, Point B, Point C) {
        int ABx = B.x - A.x;
        int ABy = B.y - A.y;
        int ACx = C.x - A.x;
        int ACy = C.y - A.y;

        return ABx * ACy - ABy * ACx;
    }

    public int getDistance(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
}

3. Time & Space Complexity

Gift Wrapping Algorithm: 时间复杂度O(n * h), n是point的个数, h是point在边界上的个数, worst case是O(n^2), 空间复杂度O(n ^ 2)