ConvexHull.cpp

#include<bits/stdc++.h> 
using namespace std; 

#define iPair pair<int, int> 

set<iPair> hull;  //  To store points of convex hull

int findSide(iPair p1, iPair p2, iPair p) 
{ 
	int val = (p.second - p1.second) * (p2.first - p1.first) - (p2.second - p1.second) * (p.first - p1.first); 
	if (val > 0) 
		return 1; 
	if (val < 0) 
		return -1; 
	return 0; 
} 

int lineDist(iPair p1, iPair p2, iPair p) 
{ 
	return abs ((p.second - p1.second) * (p2.first - p1.first) - (p2.second - p1.second) * (p.first - p1.first)); 
} 

void convexHull(iPair a[], int n, iPair p1, iPair p2, int side) 
{ 
	int ind = -1; 
	int max_dist = 0; 

	for (int i=0; i<n; i++) 
	{ 
		int temp = lineDist(p1, p2, a[i]); 
		if (findSide(p1, p2, a[i]) == side && temp > max_dist) 
		{ 
			ind = i; 
			max_dist = temp; 
		} 
	} 

	if (ind == -1) 
	{ 
		hull.insert(p1); 
		hull.insert(p2); 
		return; 
	} 
 
	convexHull(a, n, a[ind], p1, -findSide(a[ind], p1, p2)); 
	convexHull(a, n, a[ind], p2, -findSide(a[ind], p2, p1)); 
} 

void printHull(iPair a[], int n) 
{ 
	if (n < 3) 
	{ 
		cout << "Convex hull not possible\n"; 
		return; 
	} 

	int min_x = 0, max_x = 0; 
	for (int i=1; i<n; i++) 
	{ 
		if (a[i].first < a[min_x].first) 
			min_x = i; 
		if (a[i].first > a[max_x].first) 
			max_x = i; 
	} 

	convexHull(a, n, a[min_x], a[max_x], 1); 
	convexHull(a, n, a[min_x], a[max_x], -1); 

	cout << "The points in Convex Hull are:\n"; 
	for(auto x: hull) {
        cout<<"("<<x.first<<", "<<x.second<<") ";
    }
} 

int main() 
{ 
	iPair a[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}}; 
	int n = sizeof(a)/sizeof(a[0]); 
	printHull(a, n); 
	return 0; 
}