fo.cpp

#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <math.h>
 
using namespace std;
 
typedef map<double, double> MAP;
typedef MAP::iterator IT;
 
typedef struct POINT
{
	int x;
	int y;
}
POINT;
 
typedef struct DOINT
{
	double x;
	double y;
}
DOINT;
 
POINT Input[20000];
DOINT Point[20000];
 
double Queue[1000];
 
int n;
double GetPerimeter(double d)
{
	d *= (atan(1) * 4) / 180.;
 
	double xMin = 1e10, xMax = -1e10, yMin = 1e10, yMax = -1e10;
 
	for(int i = 0; i < n; i++)
	{
		double x = Input[i].x;
		double y = Input[i].y;
 
		Point[i].x = (cos(d) * x) - (sin(d) * y);
		Point[i].y = (sin(d) * x) + (cos(d) * y);
 
		if(Point[i].x < xMin) xMin = Point[i].x;
		if(Point[i].x > xMax) xMax = Point[i].x;
 
		if(Point[i].y < yMin) yMin = Point[i].y;
		if(Point[i].y > yMax) yMax = Point[i].y;
	}
 
	return 2. * ((xMax - xMin) + (yMax - yMin));
}
 
int main()
{
	while(scanf("%d", &n) > 0)
	{
		MAP Map;
		Map.clear();
 
		double rsl;
		for(int i = 0; i < n; i++)
		{
			scanf("%d%d", &(Input[i].x), &(Input[i].y));
		}
 
		double step = 90. / 1024.;
		for(double d = 0.; d <= 90.; d += step)
		{
			Map[GetPerimeter(d)] = d;
		}
 
		for(int k = 0; k < 10; k++)
		{
			step /= 64.;
			int i = 0;
			for(IT it = Map.begin(); i < 5; it++, i++)
			{
				Queue[i] = it->second;
			}
 
			for(i = 0; i < 5; i++)
			{
				double d = Queue[i];
				for(int j = -64; j <= 64; j++)
				{
					double dd = d + (j * step);
					Map[GetPerimeter(dd)] = dd;
				}
			}
		}
 
		/*for(IT it = Map.begin(); it != Map.end(); it++)
		{
			printf("%lf for %lf degrees\n", it->first, it->second);
		}*/
 
		rsl = Map.begin()->first;
		printf("%lf\n", rsl);
	}
 
	return 0;
}