* Definition for a point.
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
public List<Point> outerTrees(Point[] points) {
return Arrays.asList(points);
Point startPoint = points[0];
// Find the leftmost point as the start point
for (int i = 1; i < points.length; i++) {
if (points[i].x < startPoint.x) {
// Use Set because Gift Wrapping Algorithm may try to insert dupilcate value
Set<Point> res = new HashSet();
List<Point> collinearPoints = new ArrayList();
Point curPoint = startPoint;
int curIndex = startIndex;
Point nextPoint = points[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
// Clear collinearPoints because we change the nextPoint
// 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);
// If nextPoint is on the boundary of convex hull
// then all points in collinear points will be also on boundary.
collinearPoints.add(points[i]);
for (Point point : collinearPoints) {
// If nextPoint is the same as startPoint, we have formed an envelope and it is done.
if (nextPoint == startPoint) {
// Add nextPoint to the result and set curPoint as nextPoint
return new ArrayList<>(res);
public int getCrossProduct(Point A, Point B, Point C) {
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);