2958673_ac_343ms_136k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include "stdio.h"
#include "math.h"

const double pai = acos(-1);

struct point
{
	double x, y;
};

point pt[31];

struct line
{
	double k, b;
};

int no, n;
double min;

double max(double a,double b)
{
	return a-b > 0 ? a : b;
}

void input()
{
	int i;
	double minx, miny, maxx, maxy;

	no = 0;
	scanf("%d",&n);
	minx = miny = 600.0;
	maxx = maxy = -600.0;
	for(i = 0; i < n; i++)
	{
		scanf("%lf%lf",&pt[i].x,&pt[i].y);
		if(pt[i].x > maxx)
			maxx = pt[i].x;
		if(pt[i].x < minx)
			minx = pt[i].x;
		if(pt[i].y > maxy)
			maxy = pt[i].y;
		if(pt[i].y < miny)
			miny = pt[i].y;
	}
	min = max(maxy-miny,maxx-minx);
}

void getLine(double ang,line &l,double x,double y)
{
	l.k = tan(ang);
	l.b = y - l.k*x;
}

double getMax(line l,double ang)
{
	int i;
	double dis;
	double Max, Min;
	int a, b;

	Max = -10000;
	Min = 10000;
	for(i = 0; i < n; i++)
	{
		dis = fabs(l.k*pt[i].x-pt[i].y+l.b)/sqrt(l.k*l.k+1.0);
		if(dis < Min)
		{
			a = i;
			Min = dis;
		}
		if(dis > Max)
		{
			b = i;
			Max = dis;
		}
	}
	return Max-Min;
}

void solve()
{
	int i;
	double ang, c, c1, c2;
	line l;
	double st, ed, inc;
	double bestst, bested;

	st = 0.1;ed = 90.0;
	for(i = 0; i < 3; i++)
	{
		inc = (ed-st)/521;
		for(ang = st; ang < ed; ang += inc)
		{
			getLine(ang*pai/180.0,l,-500.0,500.0);
			c1 = getMax(l,ang*pai/180.0);
			getLine((ang+90.0)*pai/180.0,l,500.0,500.0);
			c2 = getMax(l,(ang+90.0)*pai/180.0);
			c = max(c1,c2);
			if(c < min)
			{
				min = c;
				bestst = ang-inc;
				bested = ang+inc;
			}
		}
		st = bestst;
		ed = bested;
	}
	printf("%.2lf\n",min*min);
}

int main()
{
	int t;

	scanf("%d",&t);
	while(t--)
	{
		input();
		solve();
	}
	return 0;
}