Algorithm Practice
Search…
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:
1
Input: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
2
3
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
4
5
Explanation:
Copied!
Example 2:
1
Input: [[1,2],[2,2],[4,2]]
2
3
Output: [[1,2],[2,2],[4,2]]
4
5
Explanation:
Copied!
1
Even you only have trees in a line, you need to use rope to enclose them.
Copied!
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)
1
/**
2
* Definition for a point.
3
* class Point {
4
* int x;
5
* int y;
6
* Point() { x = 0; y = 0; }
7
* Point(int a, int b) { x = a; y = b; }
8
* }
9
*/
10
class Solution {
11
public List<Point> outerTrees(Point[] points) {
12
if (points.length < 3) {
13
return Arrays.asList(points);
14
}
15
16
Point startPoint = points[0];
17
int startIndex = 0;
18
19
// Find the leftmost point as the start point
20
for (int i = 1; i < points.length; i++) {
21
if (points[i].x < startPoint.x) {
22
startPoint = points[i];
23
startIndex = i;
24
}
25
}
26
27
// Use Set because Gift Wrapping Algorithm may try to insert dupilcate value
28
Set<Point> res = new HashSet();
29
List<Point> collinearPoints = new ArrayList();
30
31
res.add(startPoint);
32
33
Point curPoint = startPoint;
34
int curIndex = startIndex;
35
36
while (true) {
37
Point nextPoint = points[0];
38
int nextIndex = 0;
39
40
for (int i = 1; i < points.length; i++) {
41
if (curIndex == i) continue;
42
43
int crossProduct = getCrossProduct(curPoint, nextPoint, points[i]);
44
// if crossProduct > 0, points[i] is on the left of line curPoint-nextPoint
45
if (crossProduct > 0) {
46
nextPoint = points[i];
47
nextIndex = i;
48
// Clear collinearPoints because we change the nextPoint
49
collinearPoints.clear();
50
}
51
// if crossProduct = 0, points[i] is collinear with curPoint and nextPoint
52
else if (crossProduct == 0) {
53
// Update nextPoint with points[i] is points[i] is further from curPoint
54
if (getDistance(curPoint, points[i]) > getDistance(curPoint, nextPoint)) {
55
collinearPoints.add(nextPoint);
56
nextPoint = points[i];
57
nextIndex = i;
58
}
59
// If nextPoint is on the boundary of convex hull
60
// then all points in collinear points will be also on boundary.
61
else {
62
collinearPoints.add(points[i]);
63
}
64
}
65
}
66
67
for (Point point : collinearPoints) {
68
res.add(point);
69
}
70
71
// If nextPoint is the same as startPoint, we have formed an envelope and it is done.
72
if (nextPoint == startPoint) {
73
break;
74
}
75
76
// Add nextPoint to the result and set curPoint as nextPoint
77
res.add(nextPoint);
78
curPoint = nextPoint;
79
curIndex = nextIndex;
80
}
81
82
return new ArrayList<>(res);
83
}
84
85
public int getCrossProduct(Point A, Point B, Point C) {
86
int ABx = B.x - A.x;
87
int ABy = B.y - A.y;
88
int ACx = C.x - A.x;
89
int ACy = C.y - A.y;
90
91
return ABx * ACy - ABy * ACx;
92
}
93
94
public int getDistance(Point p1, Point p2) {
95
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
96
}
97
}
Copied!
3. Time & Space Complexity
Gift Wrapping Algorithm: 时间复杂度O(n * h), n是point的个数, h是point在边界上的个数, worst case是O(n^2), 空间复杂度O(n ^ 2)
Last modified 2yr ago