UVa 681 - Convex Hull Finding

// UVA 681 - Convex Hull Finding

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

#define datatype signed long long int

struct point {
	datatype x, y;
};

datatype cross(point a, point b, point c) {
	datatype x1 = b.x - a.x;
	datatype x2 = c.x - a.x;
	datatype y1 = b.y - a.y;
	datatype y2 = c.y - a.y;
	return x1 * y2 - x2 * y1;
}

datatype dist(point a, point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main() {
	datatype t, dummy;
	cin >> t;
	cout << t << endl;
	for (; t; t--) {
		datatype n;
		point p[1500];
		cin >> n;
		n--;
		datatype f = 0;
		for (datatype i = 0; i < n; i++) {
			cin >> p[i].x >> p[i].y;
			if (p[i].y < p[f].y || p[i].y == p[f].y && p[i].x < p[f].x)
				f = i;
		}
		cin >> dummy >> dummy;

		bool yet[1500];
		memset(yet, true, sizeof(yet));
		yet[f] = false;
		vector<point> hull;
		hull.push_back(p[f]);
		datatype m;
		bool cont;
		do {
			cont = false;
			point last = hull[hull.size() - 1];
			m = n;
			for (datatype j = 0; j < n; j++)
				if (yet[j]) {
					m = j;
					break;
				}
			if (m < n) {
				for (datatype i = 0; i < n; i++)
					if (yet[i]) {
						datatype c = cross(last, p[m], p[i]);
						if (c < 0 || c == 0 && dist(last, p[i]) > dist(last, p[m]))
							m = i;
					}
				if (cross(last, p[f], p[m]) < 0 || (last.x == p[f].x && last.y == p[f].y)) {
					hull.push_back(p[m]);
					yet[m] = false;
					cont = true;
				}
			}
		} while (cont);

		if (hull.size() > 0) {
			cout << hull.size() + 1 << endl;
			for (datatype i = 0; i < hull.size(); i++)
				cout << hull[i].x << " " << hull[i].y << endl;
			cout << hull[0].x << " " << hull[0].y << endl;
		} else
			cout << 0 << endl;
		if (t > 1) {
			cout << -1 << endl;
			cin >> n;
		}

	}
	return 0;
}