Hull Brute Force
*******************************************************************************

#include "hull-bruteforce.h"
#include <algorithm>
#include <iostream>

bool Point::operator==( Point const& arg2 ) const {
    return ( (x==arg2.x) && (y==arg2.y) );
}

std::ostream& operator<< (std::ostream& os, Point const& p) {
	os << "(" << p.x << " , " << p.y << ") ";
	return os;
}

std::istream& operator>> (std::istream& os, Point & p) {
	os >> p.x >> p.y;
	return os;
}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//return value is (on left, on right)
std::pair<bool,bool> get_location(
		float const& p1x, //check which side of the line (p1x,p1y)-->(p2x,p2y) 
		float const& p1y, //point (qx,qy) is on
		float const& p2x,
		float const& p2y,
		float const& qx,
		float const& qy
		) 
{
	Point dir   = {p2x-p1x,p2y-p1y};
	Point norm  = {dir.y, -dir.x};
	Point point = {qx-p1x,qy-p1y};
	//scalar product is positive if on right side
	float scal_prod = norm.x*point.x + norm.y*point.y;
	return std::make_pair( (scal_prod<0), (scal_prod>0));
}

//returns a set of indices of points that form convex hull
std::set<int> hullBruteForce ( std::vector< Point > const& points )
{
	// The number of points in the set.
	int num_points = points.size();

	//std::cout << "number of points " << num_points << std::endl;
	if ( num_points < 3 ) throw "bad number of points";

	// The list of all of the indices in the convex hull.
	std::set<int> hull_indices;

	// Try each point as the first point in the set...
	for (int i = 0; i < num_points - 1; ++i)
	{
		Point P1 = points[i];

		// with every other point as the other point in the set.
		for (int j = i + 1; j < num_points; ++j)
		{
			Point P2 = points[j];

			// If the point is the same it is not a line segment.
			if (i != j)
			{
				bool addIndices = true;
				float previousResult = 0.0f;

				// Check if all of the other points are on one side of this line.
				// Break out if there were two points on different sides.
				for (int k = 0; k < num_points && addIndices; ++k)
				{
					// If this point is not one of the two making up the line segment.
					if (k != i && k != j)
					{
						Point P3 = points[k];

						// The straight line through P1 = (x1, y1), P2 = (x2, y2) 
						// can be defined by the equation ((a * x) + (b * y)) = c where,
						// a = (y2 - y1), b = (x1 - x2), c = ((x1 * y2) - (y1 * x2)).

						float a = P2.y - P1.y;
						float b = P1.x - P2.x;
						float c = (P1.x * P2.y) - (P1.y * P2.x);

						float result = (a * P3.x) + (b * P3.y);

						// Check if the point is on the positive plane side of the line segment.
						if (result > c)
						{
							// If there is a previous result and that result is on the other
							// plane, this line segment is not convex.
							if (k > 0 && previousResult < c)
							{
								addIndices = false;
							}
						}
						// Check if the point is on the negative plane side of the line segment.
						else if (result < c)
						{
							// If there is a previous result and that result is on the other
							// plane, this line segment is not convex.
							if (k > 0 && previousResult > c)
							{
								addIndices = false;
							}
						}
						// If the point is on the line segment it should not be added.
						else
						{
							addIndices = false;
						}

						previousResult = result;
					}
				}

				// Add both points from this line segment. Because hull_indices is a set 
				// we don't have to worry about adding the same index twice.
				if (addIndices)
				{
					hull_indices.insert(i);
					hull_indices.insert(j);
				}
			}
		}
	}
		
	return hull_indices;
}

std::vector<int> hullBruteForce2 ( std::vector< Point > const& points )
{
	int num_points = points.size();
	if ( num_points < 3 ) throw "bad number of points";

	std::vector<int> hull_indices;
	int firstIndex = 0; // Used to determine when we've closed the hull.
	bool hullIsClosed = false;

	// Keeps track of the previous index for validity checks.
	int previousIndex = 0;

	// Initialize our minimum x starting point to points[0] for now.
	Point P1 = points[0];

	// Find the smallest x value for any point.
	// This point is guarunteed to be on the hull.
	for (int i = 0; i < num_points; ++i)
	{
		// If this x is smaller than our previous x, update P1.
		if (points[i].x < P1.x)
		{
			P1 = points[i];
			firstIndex = i;
			previousIndex = i;
		}
	}

	// Loop until we found all of the points to make up the convex hull.
	while (!hullIsClosed)
	{
		// Use each of these points as the other end of the line segment.
		for (int j = 0; j < num_points && !hullIsClosed; ++j)
		{
			Point P2 = points[j];

			// If the point is the same it is not a line segment.
			if (P1 == P2)
			{
				continue;
			}

			bool addIndices = true;

			// Check if all of the other points are on one side of this line.
			for (int k = 0; k < num_points && addIndices; ++k)
			{
				// If this point is not one of the two making up the line segment.
				if (k != previousIndex && k != j)
				{
					Point P3 = points[k];

					// The straight line through P1 = (x1, y1), P2 = (x2, y2) 
					// can be defined by the equation ((a * x) + (b * y)) = c where,
					// a = (y2 - y1), b = (x1 - x2), c = ((x1 * y2) - (y1 * x2)).

					float a = P2.y - P1.y;
					float b = P1.x - P2.x;
					float c = (P1.x * P2.y) - (P1.y * P2.x);

					float result = (a * P3.x) + (b * P3.y);

					// If the point is to the right of the line segment or on it, 
					// this line segment is not part of the hull.
					if (result >= c)
					{
						addIndices = false;
					}
				}
			}

			// Add the second point on the line segment. The first index will 
			// be added when the line segment is found to close the hull.
			if (addIndices)
			{
				hull_indices.push_back(j);

				// Use the recently added index as the new starting point on the next loop.
				previousIndex = j;
				P1 = points[previousIndex];

				// If this recently added index is the first one we have successfully made the hull.
				if (firstIndex == j)
				{
					hullIsClosed = true;
				}
			}
		}
	}

	return hull_indices;
}


*******************************************************************************

Dijkstra
*******************************************************************************

#include "e-dijkstra.h"
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <limits>

using namespace std;

// Stores all of the values in the input file into a map.
map<int, vector<int>> ProcessFile(char const *input_file, std::map<std::pair<int, int>, int> &tree, size_t &loc, int &rech, int &edges)
{
	ifstream file;
	file.open(input_file);

	if (!file.is_open())
	{
		cout << "ERROR: File was not opened correctly." << endl;
		return map<int, vector<int>>();
	}

	// Save the number of locations, recharges, and number of edges.
	file >> loc; file >> rech; file >> edges;
	
	map<int, vector<int>> adjacencies;

	// Store the rest of the values in the map.
	while (!file.eof())
	{
		int vert1; file >> vert1;
		int vert2; file >> vert2;
		int weight; file >> weight;

		// In case the eof flag got set mid-read.
		if (file.eof())
		{
			break;
		}

		// Copy this path in both directions.
		pair<int, int> path = make_pair(vert1, vert2);
		adjacencies[vert1].push_back(vert2);
		tree.insert(make_pair(path, weight));

		pair<int, int> path2 = make_pair(vert2, vert1);
		adjacencies[vert2].push_back(vert1);
		tree.insert(make_pair(path2, weight));
	}

	file.close();

	return adjacencies;
}

bool ComparePairs(pair<int, int> pair1, pair<int, int> pair2)
{
	// Special case where recharges take priority.
	if (pair1.first < pair2.first)
	{
		return false;
	}

	return pair1.first > pair2.first || pair1.second > pair2.second;
}

bool e_dijkstra_aux(map<std::pair<int, int>, int>& tree, map<int, vector<int>>& adjacencyList,
	size_t& nLocations, int& kRecharges, int& range, size_t startindex)
{
	vector<pair<int, pair<int, int>>> closedList;
	vector<pair<int, pair<int, int>>> openList;

	// Pick any node and put it on the openList.
	openList.push_back(make_pair(startindex, make_pair(kRecharges, range)));

	// Continue until there is nothing left on the open list.
	while (!openList.empty())
	{
		int cheapestNode = -1;
		int maxCharges = numeric_limits<int>::min();
		int maxCharge = numeric_limits<int>::min();
		int index = 0;

		// Find the cheapest openList node.
		for (size_t i = 0; i < openList.size(); ++i)
		{
			// If we have a cheaper value store it.
			if (!ComparePairs(make_pair(maxCharges, maxCharge), openList[i].second))
			{
				cheapestNode = openList[i].first;
				maxCharges = openList[i].second.first;
				maxCharge = openList[i].second.second;
				index = i;
			}
		}

		// Take any adjacent nodes and put them on the openList.
		vector<int> adjacentNodes = adjacencyList[cheapestNode];

		// Put all of the nodes adjacent to the cheapest one on the openList.
		for (size_t i = 0; i < adjacentNodes.size(); ++i)
		{
			int cost = tree[make_pair(cheapestNode, adjacentNodes[i])];

			int numRecharges = openList[index].second.first;
			int chargesAfterTravel = numRecharges;

			int currentCharge = openList[index].second.second;
			int chargeAfterTravel = currentCharge - cost;

			// If this trip would use the charge up, recharge the battery.
			if (chargeAfterTravel < 0)
			{
				--chargesAfterTravel;
				chargeAfterTravel = range - cost;

				// If this is no longer a valid charge amount ignore this one.
				if (chargesAfterTravel < 0 || chargeAfterTravel < 0)
				{
					continue;
				}
			}

			int ignoreNode = false;

			// Check if the car can even go that far in between vertices.
			if (cost <= range)
			{
				// If this node is already on the closedList ignore it.
				for (size_t j = 0; j < closedList.size(); ++j)
				{
					if (adjacentNodes[i] == closedList[j].first)
					{
						// If the cost for travel factoring in recharges is better or worse.
						if (!ComparePairs(make_pair(chargesAfterTravel, chargeAfterTravel), closedList[j].second))
						{
							ignoreNode = true;
							break;
						}
					}
				}

				// If this is a new node put it on the openList.
				if (!ignoreNode)
				{
					openList.push_back(make_pair(adjacentNodes[i], make_pair(chargesAfterTravel, chargeAfterTravel)));
					ignoreNode = false;
				}
			}
		}

		int closedListEntry = -1;
		pair<int, int> cLECost = make_pair(-1, -1);

		// Find if there is a value at that node already in the closed list.
		for (size_t i = 0; i < closedList.size(); ++i)
		{
			if (cheapestNode == closedList[i].first)
			{
				closedListEntry = closedList[i].first;
				cLECost = closedList[i].second;
				break;
			}
		}

		// If our new entry in the close list is cheaper replace it.
		if (closedListEntry == -1)
		{
			closedList.push_back(make_pair(cheapestNode, make_pair(maxCharges, maxCharge)));
		}
		else if (ComparePairs(make_pair(maxCharges, maxCharge), closedList[closedListEntry].second))
		{
			// Put the cheapest cost on the closedList.
			closedList[closedListEntry].second = make_pair(maxCharges, maxCharge);
		}

		openList.erase(openList.begin() + index);
	}

	// If the number of locations matches the closed list we can visit every city.
	if (closedList.size() == nLocations)
	{
		return true;
	}

	return false;
}

// This function finds if a hypothetical car that can go the distance of range
// can make it to every vertex from every other vertex with the given number of
// charges. The vertices can be thought of as cities.
bool e_dijkstra(char const* input_file, int range)
{
	size_t nLocations = 0;
	int kRecharges = 0, mNumberOfEdges = 0;

	// The pair is vertices to vertices, and the other int is the weight of the path.
	map<std::pair<int, int>, int> tree;

	// The list of which nodes are connected to each other.
	map<int, vector<int>> adjacencyList =
		ProcessFile(input_file, tree, nLocations, kRecharges, mNumberOfEdges);

	// The vehicle starts empty so remove one to start.
	--kRecharges;

	// Try every vertices.
	for (size_t i = 0; i < nLocations; ++i)
	{
		bool status = e_dijkstra_aux(tree, adjacencyList, nLocations, kRecharges, range, i);
		
		if (!status)
		{
			return status;
		}
	}

	return true;
}


*******************************************************************************

Closest Pair Divide & Conquer
*******************************************************************************

#include "closestpair.h"
#include <algorithm>
#include <limits>
#include <cmath>
#include <iostream>
#include <utility>

std::ostream& operator<< (std::ostream& os, Point const& p) {
	os << "(" << p.x << " , " << p.y << ") ";
	return os;
}

std::istream& operator>> (std::istream& os, Point & p) {
	os >> p.x >> p.y;
	return os;
}

////////////////////////////////////////////////////////////////////////////////
float closestPair_aux(std::vector<Point> const& points, int left, int right);

////////////////////////////////////////////////////////////////////////////////
float Distance(Point p1, Point p2)
{
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

////////////////////////////////////////////////////////////////////////////////
float FindMin(std::vector<Point> points)
{
	// Initialize to float max to ensure that we find a lower value.
	float min = std::numeric_limits<float>::max();

	for (size_t i = 0; i < points.size(); ++i)
	{
		// Initialize to i + 1 because we don't want to compare the distance 
		// to the same point.
		for (size_t j = i + 1; j < points.size(); ++j)
		{
			float dist = Distance(points[i], points[j]);

			if (dist < min)
			{
				min = dist;
			}
		}
	}

	return min;
}

////////////////////////////////////////////////////////////////////////////////
bool CompareX(const Point& point1, const Point& point2)
{
	// If the first point's x value is smaller return true.
	if (point1.x < point2.x)
	{
		return true;
	}

	// Otherwise return false
	return false;
}

////////////////////////////////////////////////////////////////////////////////
bool CompareY(const Point& point1, const Point& point2)
{
	// If the first point's y value is smaller return true.
	if (point1.y < point2.y)
	{
		return true;
	}

	// Otherwise return false
	return false;
}

////////////////////////////////////////////////////////////////////////////////
float closestPair (std::vector<Point> const& points)
{
	int size = points.size();

	if (size == 0) throw "zero size subset";
	if (size == 1) return std::numeric_limits<float>::max();

	// Copy the array of points since the one we are passed is const.
	std::vector<Point> Points = points;

	// Sort all of the points according to x.
	std::sort(Points.begin(), Points.end(), CompareX);

	return closestPair_aux(Points, 0, size);
}

////////////////////////////////////////////////////////////////////////////////
float closestPair_aux(std::vector<Point> const& points, int left, int right)
{
	// A copy of the points array with the new size.
	std::vector<Point> Points(points.begin() + left, points.begin() + right);

	int size = Points.size();

	if (size == 0) throw "zero size subset";
	if (size == 1) return std::numeric_limits<float>::max();
	
	// If there are two or three points use the brute force method.
	if (size <= 3)
	{
		return FindMin(Points);
	}

	// Find the midpoint.
	int middle = size / 2;
	Point midPoint = Points[middle];

	// Find the smallest distance in each sub-array.
	float lDist = closestPair_aux(points, left, left + middle);
	float rDist = closestPair_aux(points, left + middle, right);

	// Pick the smallest of the two distances.
	float minDist = std::min(lDist, rDist);

	std::vector<Point> Strip;
	int j = 0;

	// Find all of the points in the strip of space between the two sub-arrays 
	// that are d distance from each other or less.
	for (int i = 0; i < size; ++i)
	{
		if (abs(Points[i].x - midPoint.x) < minDist)
		{
			Strip.push_back(Points[i]);
			++j;
		}
	}

	// Find the smallest distance in strip.
	std::sort(Strip.begin(), Strip.end(), CompareY);
	int stripSize = Strip.size();

	for (int i = 0; i < stripSize; ++i)
	{
		for (int j = i + 1; j < stripSize && (Strip[j].y - Strip[i].y) < minDist; ++j)
		{
			if (Distance(Strip[i], Strip[j]) < minDist)
			{
				minDist = Distance(Strip[i], Strip[j]);
			}
		}
	}

	// Return the smallest distance found in this sub-array.
	return minDist;
}


*******************************************************************************