Quick Hull Algo wish hand-craft HashTable.

gistfile1.cpp

// C++0x
#include <cstring>
#include <vector>
#include <string>
#include <climits>

using namespace std;

class pairSet {
	const static unsigned int hSize = 100003;
	struct node {
		node(pair<int, int> data, node * next) : data{data}, next{next} {}
		pair<int, int> data;
		node * next;
	};
	node * h[hSize];
public:
	vector<pair<int, int>> elem;
	pair<int, int> min, max;
	pairSet() : min{make_pair(INT_MAX, INT_MAX)}, max{make_pair(INT_MIN, INT_MIN)} {
		memset(h, 0, sizeof(node *) * hSize);
	}

	void insert(const pair<int, int> item) {
		unsigned long long idx = (((unsigned long long)(item.first) << 32) + (unsigned long long)(item.second)) % hSize;
		for (node * iter = h[idx]; iter != nullptr; iter = iter->next) {
			if (iter->data == item) {
				return;
			}
		}
		h[idx] = new node{item, h[idx]};
		elem.push_back(item);
		if (item < min) {
			min = item;
		}
		if (item > max) {
			max = item;
		}
	}
};

long long cProduct(pair<int, int> a, pair<int, int> b, pair<int, int> c) { // -1 : right, 0 : direct, 1 : left
	return ((long long)b.first - (long long)a.first) * ((long long)c.second - (long long)b.second) - ((long long)c.first - (long long)b.first) * ((long long)b.second - (long long)a.second);
}

inline
unsigned long long calcArea(const pair<int, int> a, const pair<int, int> b, const pair<int, int> c) {
	return abs(cProduct(a, b, c));
}

inline
bool sameSign(long long a, long long b) {
	return ((a < 0 && b < 0) || (a > 0 && b > 0) || (a == 0 && b == 0));
}

struct convSet {
	vector<pair<int, int>> & v;
	vector<pair<int, int>> cv;
	pair<int, int> min, max;

	convSet(vector<pair<int, int>> & elem, pair<int, int> min, pair<int, int> max) : v(elem), min(min), max(max) {}

	unsigned long long getArea() {
		if (v.size() <= 1) {
			cv = v;
			return 0;
		}
		auto l = min, r = max;
		unsigned int len = v.size();
		unsigned int ll = 0, rr = len;
		unsigned int i = 0;
		while (i < rr) {
			if (cProduct(l, v[i], r) < 0) {
				swap(v[ll], v[i]);
				ll++;
				i++;
			} else if (cProduct(l, v[i], r) > 0) {
				rr--;
				swap(v[rr], v[i]);
			} else {
				i++;
			}
		}
		cv.push_back(l);
		auto ret = calc(l, r, 0, ll);
		cv.push_back(r);
		ret += calc(r, l, rr, len);
		return ret;
	}

	unsigned long long calc(pair<int, int> a, pair<int, int> b, unsigned int l, unsigned int r) {
		if (l == r) {
			return 0;
		}
		unsigned long long area = calcArea(v[l], a, b);
		pair<int, int> o = v[l];
		for (unsigned int i = l + 1; i < r; i++) {
			auto tArea = calcArea(v[i], a, b);
			if (area < tArea) {
				area = tArea;
				o = v[i];
			}
		}
		if (area == 0) {
			return 0;
		}
		unsigned int ll = l, rr = r;
		unsigned int i = l;
		while (i < rr) {
			auto temp = cProduct(a, v[i], b);
			if (sameSign(cProduct(a, v[i], o), temp)) {
				swap(v[i], v[ll]);
				ll++;
				i++;
			} else if (sameSign(cProduct(o, v[i], b), temp)) {
				rr--;
				swap(v[i], v[rr]);
			} else {
				i++;
			}
		}
		area += calc(a, o, l, ll);
		cv.push_back(o);
		area += calc(o, b, rr, r);
		return area;
	}
};