fo.cpp

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
 
typedef unsigned int uint;
typedef long double number;
 
struct point {
	number x, y;
 
	point():
		x(0.0),
		y(0.0) {
	}
 
	point(number x, number y):
		x(x),
		y(y) {
	}
};
 
bool operator== (const point& a, const point& b) {
	return a.x == b.x && a.y == b.y;
}
 
bool operator!= (const point& a, const point& b) {
	return a.x != b.x || a.y != b.y;
}
 
bool operator< (const point& a, const point& b) {
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}
 
bool operator> (const point& a, const point& b) {
	return a.x == b.x ? a.y > b.y : a.x > b.x;
}
 
number cross(const point& a, const point& b, const point& c) {
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
number dist(const point& a, const point& b) {
	number dx = b.x - a.x;
	number dy = b.y - a.y;
	if (dx == 0.0 && dy == 0.0)
		return 0.0;
 
	return sqrt( dx * dx + dy * dy );
}
 
point center(const point& p1, const point& p2, const point& far) {
	if (p1.x == p2.x)
		return point(p1.x, far.y);
	if (p1.y == p2.y)
		return point(far.x, p1.y);
 
	number k = (p2.y - p1.y) / (p2.x - p1.x);
	number kperp = (p1.x - p2.x) / (p2.y - p1.y);
	number d = p2.y - k * p2.x;
	number dperp = far.y - kperp * far.x;
	number xint = (d - dperp) / (kperp - k);
	number yint = kperp * xint + dperp;
	return point(xint, yint);
}
 
void obtainconvexhull(std::vector<point>& hull, std::vector<point>& points) {
	std::sort(points.begin(), points.end());
	hull.push_back(points[0]);
	uint last_added = 0;
	uint ref;
 
	do
	{
		ref = 0;
		for (uint j = 0; j < points.size(); j++)
		{
			int wedge = cross(hull[last_added], points[ref], points[j]);
			if (points[ref] == hull[last_added] || wedge < 0)
				ref = j;
		}
		if (ref != 0)
		{
			hull.push_back(points[ref]);
			points.erase(points.begin()+ref);
			last_added++;
		}
	}
	while (ref != 0);
}
 
number getminwidth(std::vector<point>& polygon) {
	uint aux = polygon.size();
	number minwidthoverall = INT_MAX; // WHAT?
	for (uint i = 0; i < aux; i++)
	{
		number maxwidthforoneside = 0.0;
		point maxc;
		point lineA = polygon[i];
		point lineB = polygon[(i + 1) % aux];
 
		for (uint j = 0; j < aux; j++)
			if (polygon[j] != lineA && polygon[j] != lineB)
			{
				point c = center(lineA, lineB, polygon[j]);
				number d = dist(c, polygon[j]);
				//~ if (d > 21213212)
					//~ printf("bad: c.x=%Lf, c.y=%Lf, pol[j].x=%Lf, pol[j].y=%Lf\n", c.x, c.y, polygon[j].x, polygon[j].y);
				if (maxwidthforoneside < d)
				{
					maxwidthforoneside = d;
					maxc = polygon[j];
				}
			}
 
		number left = 0.0; // product < 0
		number right = 0.0; // product > 0
		point ab = center(lineA, lineB, maxc);
		for (uint j = 0; j < aux; j++)
		{
			if (maxc == polygon[j])
				continue;
 
			point c = center(maxc, ab, polygon[j]);
			number d = dist(c, polygon[j]);
			number product = cross(maxc, ab, polygon[j]);
			if (product < 0)
				left = std::max(left, d);
			if (product > 0)
				right = std::max(right, d);
		}
 
		//~ printf("current minwidth: %Lf\n", minwidthoverall);
		//~ printf("maxwidthforoneside: %Lf, left: %Lf, right: %Lf\n", maxwidthforoneside, left, right);
		minwidthoverall = std::min(minwidthoverall, maxwidthforoneside * 2 + (left + right) * 2);
		//~ printf("new minwidth: %Lf\n\n", minwidthoverall);
	}
	return minwidthoverall;
}
 
int main() {
	int vertices;
 
	while (true)
	{
		if (1 != scanf("%d", &vertices))
			break;
 
		std::vector<point> polygon;
		while (vertices--)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			polygon.push_back(point(number(x), number(y)));
		}
 
		std::vector<point> convexhull;
		obtainconvexhull(convexhull, polygon);
		number answertoeverything = getminwidth(convexhull);
 
		printf("%Lf\n", answertoeverything);
	}
 
	return 0;
}