#include <iostream>
#include <vector>
#include <algorithm>

struct Point {
	float x;
	float y;
};

// returns cross product p0p1 x p0p2
float direction(Point p0, Point p1, Point p2) {
	return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

// returns squared distance between given points
float distSquared(Point a, Point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

std::vector<Point> FindConvexHull(std::vector<Point> &points) {
	// find minimum point
	auto minimumIterator = std::min_element(points.begin(), points.end(), [](Point a, Point b) {
		return a.y < b.y || (a.y == b.y && a.x < b.x);
	});
	// and swap it with the beginning of points vector
	std::iter_swap(points.begin(), minimumIterator);

	// sort the rest of the points based on orientation to minimum point (and on distance for same orientations)
	std::sort(points.begin() + 1, points.end(), [=](Point a, Point b) {
		float d = direction(points[0], a, b);
		return d ? d > 0 : distSquared(points[0], a) < distSquared(points[0], b);
	});

	// add first 3 points to convex hull
	std::vector<Point> convexHull;
	convexHull.push_back(points[0]);
	convexHull.push_back(points[1]);
	convexHull.push_back(points[2]);
	for (int i = 3; i < points.size(); ++i) {
		// while going through points:
		//  convexHull[last-1], convexHull[last], points[i]
		// there is no left turn
		while (direction(convexHull[convexHull.size() - 2], convexHull.back(), points[i]) <= 0) {
			// remove last point from convex hull
			convexHull.pop_back();
		}
		// now there is left turn so add current point to convex hull
		convexHull.push_back(points[i]);
	}
	return convexHull;
}

int main(int argc, char *argv[]) {
	std::vector<Point> points = {
		{ 1,4 },{ 2,1 },{ 2,5 },{ 3,3 },{ 4,2 },{ 4,7 },{ 5,4 },{ 5,6 },
		{ 6,5 },{ 6,7 },{ 7,3 },{ 8,2 },{ 8,5 }
	};
	std::vector<Point> convexHull = FindConvexHull(points);
	for (auto p : convexHull) {
		std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
	}
	return 0;
}