Convex Hull

 Adobe Goldman Sachs Morgan Stanley Ola Cabs Samsung

Hard 

---

Convex Hull of a set of points, in 2D plane, is a convex polygon with minimum area such that each point lies either on the boundary of polygon or inside it. Now given a set of points the task is to find the convex hull of points.
 

Example 1:

Input: points_list = {{1,2},{3,1},{5,6}}
Output: {{1,2},{3,1},{5,6}}

Example 2:

Input : points_list = {{5,1},{4,4},{1,2}}
Output: {{1,2},{4,4},{5,1}}

 

Your Task:
You don't need to read or print anything. Your task is to complete the function FindConvexHull() which takes points_list as input parameter and returns Convex Hull of given points in a list. If not possible returns a list containing -1.
 

Expected Time Complexity: O(nlog(n))
Expected Space Complexity: O(n) where n = total no. of points

Constraints:
1 <= n <= 104
-105 <= x, y <= 105

Code:

// A C++ program to find convex hull of a set of points. Refer

// https://www.geeksforgeeks.org/orientation-3-ordered-points/

// for explanation of orientation()

#include <bits/stdc++.h>

using namespace std;

struct Point

{

int x, y;

};

// To find orientation of ordered triplet (p, q, r).

// The function returns following values

// 0 --> p, q and r are collinear

// 1 --> Clockwise

// 2 --> Counterclockwise

int orientation(Point p, Point q, Point r)

{

int val = (q.y - p.y) * (r.x - q.x) -

(q.x - p.x) * (r.y - q.y);

if (val == 0) return 0; // collinear

return (val > 0)? 1: 2; // clock or counterclock wise

}

// Prints convex hull of a set of n points.

void convexHull(Point points[], int n)

{

// There must be at least 3 points

if (n < 3) return;

// Initialize Result

vector<Point> hull;

// Find the leftmost point

int l = 0;

for (int i = 1; i < n; i++)

if (points[i].x < points[l].x)

l = i;

// Start from leftmost point, keep moving counterclockwise

// until reach the start point again. This loop runs O(h)

// times where h is number of points in result or output.

int p = l, q;

do

{

// Add current point to result

hull.push_back(points[p]);

// Search for a point 'q' such that orientation(p, q,

// x) is counterclockwise for all points 'x'. The idea

// is to keep track of last visited most counterclock-

// wise point in q. If any point 'i' is more counterclock-

// wise than q, then update q.

q = (p+1)%n;

for (int i = 0; i < n; i++)

{

// If i is more counterclockwise than current q, then

// update q

if (orientation(points[p], points[i], points[q]) == 2)

q = i;

}

// Now q is the most counterclockwise with respect to p

// Set p as q for next iteration, so that q is added to

// result 'hull'

p = q;

} while (p != l); // While we don't come to first point

// Print Result

for (int i = 0; i < hull.size(); i++)

cout << "(" << hull[i].x << ", "

<< hull[i].y << ")\n";

}

// Driver program to test above functions

int main()

{

Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},

{3, 0}, {0, 0}, {3, 3}};

int n = sizeof(points)/sizeof(points[0]);

convexHull(points, n);

return 0;

}