8000 refactor 587 · Purva7/Leetcode@0911604 · GitHub
[go: up one dir, main page]
Skip to content

Commit 0911604

Browse files
fishercoder1534fishercoder1534
committed
refactor 587
1 parent 31693bd commit 0911604

File tree

1 file changed

+65
-62
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+65
-62
lines changed

‎src/main/java/com/fishercoder/solutions/_587.java

Lines changed: 65 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -35,79 +35,82 @@
3535
Input points have NO order. No order required for output.
3636
*/
3737
public class _587 {
38-
39-
/**credit: https://discuss.leetcode.com/topic/89323/java-solution-convex-hull-algorithm-gift-wrapping-aka-jarvis-march
40-
*
41-
* There are couple of ways to solve Convex Hull problem. https://en.wikipedia.org/wiki/Convex_hull_algorithms
42-
The following code implements Gift wrapping aka Jarvis march algorithm
43-
https://en.wikipedia.org/wiki/Gift_wrapping_algorithm and
44-
also added logic to handle case of multiple Points in a line
45-
because original Jarvis march algorithm assumes no three points are collinear.
46-
It also uses knowledge in this problem https://leetcode.com/problems/convex-polygon.
47-
Disscussion: https://discuss.leetcode.com/topic/70706/beyond-my-knowledge-java-solution-with-in-line-explanation*/
48-
public List<Point> outerTrees(Point[] points) {
49-
Set<Point> result = new HashSet<>();
50-
51-
// Find the leftmost point
52-
Point first = points[0];
53-
int firstIndex = 0;
54-
for (int i = 1; i < points.length; i++) {
55-
if (points[i].x < first.x) {
56-
first = points[i];
57-
firstIndex = i;
58-
}
59-
}
60-
result.add(first);
61-
62-
Point cur = first;
63-
int curIndex = firstIndex;
64-
do {
65-
Point next = points[0];
66-
int nextIndex = 0;
38+
public static class Solution1 {
39+
40+
/**
41+
* credit: https://discuss.leetcode.com/topic/89323/java-solution-convex-hull-algorithm-gift-wrapping-aka-jarvis-march
42+
* There are couple of ways to solve Convex Hull problem. https://en.wikipedia.org/wiki/Convex_hull_algorithms
43+
* The following code implements Gift wrapping aka Jarvis march algorithm
44+
* https://en.wikipedia.org/wiki/Gift_wrapping_algorithm and
45+
* also added logic to handle case of multiple Points in a line
10000
46+
* because original Jarvis march algorithm assumes no three points are collinear.
47+
* It also uses knowledge in this problem https://leetcode.com/problems/convex-polygon.
48+
* Disscussion: https://discuss.leetcode.com/topic/70706/beyond-my-knowledge-java-solution-with-in-line-explanation
49+
*/
50+
public List<Point> outerTrees(Point[] points) {
51+
Set<Point> result = new HashSet<>();
52+
53+
// Find the leftmost point
54+
Point first = points[0];
55+
int firstIndex = 0;
6756
for (int i = 1; i < points.length; i++) {
68-
if (i == curIndex) {
69-
continue;
70-
}
71-
int cross = crossProductLength(cur, points[i], next);
72-
if (nextIndex == curIndex || cross > 0
73-
// Handle collinear points
74-
|| (cross == 0 && distance(points[i], cur) > distance(next, cur))) {
75-
next = points[i];
76-
nextIndex = i;
57+
if (points[i].x < first.x) {
58+
first = points[i];
59+
firstIndex = i;
7760
}
7861
}
79-
// Handle collinear points
80-
for (int i = 0; i < points.length; i++) {
81-
if (i == curIndex) {
82-
continue;
62+
result.add(first);
63+
64+
Point cur = first;
65+
int curIndex = firstIndex;
66+
do {
67+
Point next = points[0];
68+
int nextIndex = 0;
69+
for (int i = 1; i < points.length; i++) {
70+
if (i == curIndex) {
71+
continue;
72+
}
73+
int cross = crossProductLength(cur, points[i], next);
74+
if (nextIndex == curIndex || cross > 0
75+
// Handle collinear points
76+
|| (cross == 0 && distance(points[i], cur) > distance(next, cur))) {
77+
next = points[i];
78+
nextIndex = i;
79+
}
8380
}
84-
int cross = crossProductLength(cur, points[i], next);
85-
if (cross == 0) {
86-
result.add(points[i]);
81+
// Handle collinear points
82+
for (int i = 0; i < points.length; i++) {
83+
if (i == curIndex) {
84+
continue;
85+
}
86+
int cross = crossProductLength(cur, points[i], next);
87+
if (cross == 0) {
88+
result.add(points[i]);
89+
}
8790
}
88-
}
8991

90-
cur = next;
91-
curIndex = nextIndex;
92+
cur = next;
6DB6 93+
curIndex = nextIndex;
9294

93-
} while (curIndex != firstIndex);
95+
} while (curIndex != firstIndex);
9496

95-
return new ArrayList<>(result);
96-
}
97+
return new ArrayList<>(result);
98+
}
9799

98-
private int crossProductLength(Point A, Point B, Point C) {
99-
// Get the vectors' coordinates.
100-
int BAx = A.x - B.x;
101-
int BAy = A.y - B.y;
102-
int BCx = C.x - B.x;
103-
int BCy = C.y - B.y;
100+
private int crossProductLength(Point A, Point B, Point C) {
101+
// Get the vectors' coordinates.
102+
int BAx = A 9E12 .x - B.x;
103+
int BAy = A.y - B.y;
104+
int BCx = C.x - B.x;
105+
int BCy = C.y - B.y;
104106

105-
// Calculate the Z coordinate of the cross product.
106-
return (BAx * BCy - BAy * BCx);
107-
}
107+
// Calculate the Z coordinate of the cross product.
108+
return (BAx * BCy - BAy * BCx);
109+
}
108110

109-
private int distance(Point p1, Point p2) {
110-
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
111+
private int distance(Point p1, Point p2) {
112+
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
113+
}
111114
}
112115

113116
}

0 commit comments

Comments
 (0)
0