UVa 218 - Moth Eradication

// UVa 218 - Moth Eradication

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
using namespace std;

struct point {
	double x, y;
	double angle;
};

vector<point> p;

bool operator <(point a, point b) {
	return a.angle < b.angle;
}

double ccw(point p0, point p1, point p2) {
	return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

void swap(int i, int j) {
	point c = p[i];
	p[i] = p[j];
	p[j] = c;
}

int main() {
	int n, t = 0;
	while (cin >> n && n) {
		t++;
		p.clear();
		int mn = 0;
		for (int i = 0; i < n; i++) {
			double x, y;
			cin >> x >> y;
			p.push_back( { x, y, 0 });
			if (p[i].y < p[mn].y || (p[i].y == p[mn].y && p[i].x < p[mn].x))
				mn = i;
		}
		p.push_back(p[0]);
		if (mn == 0)
			mn = n;
		swap(1, mn);

		for (int i = 2; i <= n; i++) {
			if (p[i].x == p[1].x)
				p[i].angle = M_PI / 2;
			else {
				p[i].angle = atan((p[i].y - p[1].y) / (p[i].x - p[1].x));
				while (p[i].angle < 0)
					p[i].angle += M_PI;
			}
		}
		sort(p.begin() + 2, p.end());
		p[0] = p[n];

		int m = 1;
		for (int i = 2; i <= n; i++) {
			while (ccw(p[m - 1], p[m], p[i]) <= 0) {
				if (m > 1)
					m--;
				else if (i == n)
					break;
				else
					i++;
			}
			m++;
			swap(m, i);
		}

		double P = 0;
		//p[0] = p[m];

		if (t > 1)
			cout << endl;
		printf("Region #%d:\n", t);
		for (int i = m; i > 0; i--) {
			printf("(%.1f,%.1f)-", p[i].x, p[i].y);
			P += sqrt((p[i].x - p[i - 1].x) * (p[i].x - p[i - 1].x) + (p[i].y - p[i - 1].y) * (p[i].y - p[i - 1].y));
		}
		printf("(%.1f,%.1f)\n", p[0].x, p[0].y);
		printf("Perimeter length = %.2f\n", P);

	}
	return 0;
}