Created
September 11, 2018 07:39
-
-
Save ajaynitt/b64a0dba20bf1737131a59017289bd0c to your computer and use it in GitHub Desktop.
erect the fence | convex hull problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//https://leetcode.com/problems/erect-the-fence/description/ | |
import java.util.ArrayList; | |
import java.util.HashSet; | |
import java.util.List; | |
/** | |
* Created by ajaykumar.yadav on 11/09/18. | |
**/ | |
class Point { | |
int x; | |
int y; | |
Point() { | |
x = 0; | |
y = 0; | |
} | |
Point(int a, int b) { | |
x = a; | |
y = b; | |
} | |
} | |
class Solution { | |
public int orientation(Point p, Point q, Point r) { | |
return (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); | |
} | |
public boolean inBetween(Point p, Point i, Point q) { | |
boolean a = i.x >= p.x && i.x <= q.x || i.x <= p.x && i.x >= q.x; | |
boolean b = i.y >= p.y && i.y <= q.y || i.y <= p.y && i.y >= q.y; | |
return a && b; | |
} | |
public List<Point> outerTrees(Point[] points) { | |
HashSet<Point> hull = new HashSet<>(); | |
//first find leftmost point index | |
int leftMostPoint = 0; | |
int arrLength = points.length; | |
for (int i = 0; i < arrLength; i++) { | |
if (points[i].x < points[leftMostPoint].x) { | |
leftMostPoint = i; | |
} | |
} | |
//left most point is decided by this time | |
int currentLeftMostPoint = leftMostPoint; | |
do { | |
//find next probablepoint | |
int nextPoint = (currentLeftMostPoint + 1) % arrLength; | |
//now check if there is any point which is in left of line joining leftMostPoint and nextPoint | |
for (int i = 0; i < arrLength; i++) { | |
if (orientation(points[currentLeftMostPoint], points[nextPoint], points[i]) < 0) { | |
nextPoint = i; | |
} | |
} | |
//check for colinear points , if they | |
for (int i = 0; i < arrLength; i++) { | |
if (i != currentLeftMostPoint && i != nextPoint && (orientation(points[currentLeftMostPoint], points[nextPoint], points[i]) == 0) && inBetween(points[currentLeftMostPoint], points[i], points[nextPoint])) { | |
hull.add(points[i]); | |
} | |
} | |
//add next pint to solution | |
hull.add(points[nextPoint]); | |
//move currnetLeftMostPoint | |
currentLeftMostPoint = nextPoint; | |
} while (currentLeftMostPoint != leftMostPoint); | |
return new ArrayList<>(hull); | |
} | |
public static void main(String[] args) { | |
List<Point> listPoint = new ArrayList<>(); | |
Point p1 = new Point(0, 0); | |
Point p2 = new Point(0, 10); | |
Point p3 = new Point(5, 0); | |
Point p4 = new Point(6, 18); | |
Point p5 = new Point(3, 3); | |
listPoint.add(p1); | |
listPoint.add(p2); | |
listPoint.add(p3); | |
listPoint.add(p4); | |
listPoint.add(p5); | |
Object[] pArray = listPoint.toArray(); | |
Point[] pointArray = new Point[5]; | |
for (int i = 0; i < pArray.length; i++) { | |
pointArray[i] = (Point) pArray[i]; | |
} | |
List<Point> lp = new Solution().outerTrees(pointArray); | |
lp.stream().forEach(e -> { | |
System.out.println(e.x + " "+e.y); | |
}); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment