3171509_ac_171ms_268k.cc

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

#include <stdio.h>
#include <math.h>
#define MAX 311
#define eps 1e-6

struct point
{
	double x, y;
};

struct polygon
{
	int n;
	point pt[MAX];
};

struct line
{
	double a, b, c;
};

double cross(point a,point b,point c)
{
	return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

line getLine(point a,point b)
{
	line ret;

	ret.a = b.y-a.y;
	ret.b = a.x-b.x;
	ret.c = b.x*a.y-b.y*a.x;
	return ret;
}

point line_intersection(line l1,line l2)
{
	point ret;

	if(fabs(l1.b)<1e-10)
	{
		ret.x = -l1.c/l1.a;
		ret.y = (-l2.c-l2.a*ret.x)/l2.b;
	}
	else
	{
		ret.x = (l1.c*l2.b-l1.b*l2.c)/(l1.b*l2.a-l2.b*l1.a);
		ret.y = (-l1.c-l1.a*ret.x)/l1.b;
	}
	return ret;
}

int isequal(point a,point b)
{
	if(a.x!=b.x||a.y!=b.y)
		return 0;
	return 1;
}

polygon polygon_cross(point a,point b,polygon p)
{
	int i;
	polygon newp;
	double v1, v2;
	line l1, l2;

	newp.n = 0;
	for(i = 0; i < p.n; i++)
	{
		v1 = cross(b,p.pt[i],a);
		v2 = cross(b,p.pt[i+1],a);
		if(v1==0&&v2==0)
		{
			newp.pt[newp.n++] = p.pt[i];
			newp.pt[newp.n++] = p.pt[i+1];
		}
		else
		{
			if(v1<0&&v2<0)
			{
				newp.pt[newp.n++] = p.pt[i];
				newp.pt[newp.n++] = p.pt[i+1];
			}
			else
			{
				if(v1*v2<=0)
				{
					l1 = getLine(a,b);
					l2 = getLine(p.pt[i],p.pt[i+1]);
					point intersection;
					intersection = line_intersection(l1,l2);
					if(v1 <= 0)
					{
						newp.pt[newp.n++] = p.pt[i];
						newp.pt[newp.n++] = intersection;
					}
					else
					{
						newp.pt[newp.n++] = intersection;
						newp.pt[newp.n++] = p.pt[i+1];
					}
				}
			}
		}
	}
	p.n = 0;
	if(newp.n==0)
		return p;
	p.pt[p.n++] = newp.pt[0];
	for(i = 1;i < newp.n;i++)
	{
		if(!isequal(newp.pt[i],newp.pt[i - 1]))
		{
			p.pt[p.n++] = newp.pt[i];
		}     
	}
	if(p.n!=1&&isequal(p.pt[p.n-1],p.pt[0]))
		p.n--;
	p.pt[p.n] = p.pt[0];
	return p;
}

int main()
{
	int i, fail;
	double min, mid, max;
	polygon p, newp;
	point a, b;
	double alpha, deltax;
	double minx, miny;

	while(scanf("%d",&p.n),p.n)
	{
		minx = miny = 10000;
		for(i = p.n-1; i >= 0; i--)
		{
			scanf("%lf%lf",&p.pt[i].x,&p.pt[i].y);
			if(p.pt[i].x < minx)	minx = p.pt[i].x;
			if(p.pt[i].y < miny)	miny = p.pt[i].y;
		}
		p.pt[p.n] = p.pt[0];
		min = 0.0;	
		max = 15000.0;
		while(max - min > eps)
		{
			mid = (min + max) / 2.0;
			newp = p;
			fail = 0;
			for(i = 0; i < p.n; i++)
			{
				a = p.pt[i];
				b = p.pt[i+1];
				if(a.x==b.x)
				{
					if(a.x==minx)
					{
						a.x += mid;
						b.x += mid;
					}
					else
					{
						a.x -= mid;
						b.x -= mid;
					}
				}
				else
				{
					if(a.y==b.y)
					{
						if(a.y==miny)
						{
							a.y += mid;
							b.y += mid;
						}
						else
						{
							a.y -= mid;
							b.y -= mid;
						}
					}
					else
					{
						alpha = atan((b.y-a.y)/(b.x-a.x));
						deltax = mid/sin(alpha);
						point c, d;
						c = a;
						d = b;
						c.x = a.x - deltax;
						d.x = b.x - deltax;
						a.x += deltax;
						b.x += deltax;
						if(cross(p.pt[i],p.pt[(i+2)%p.n],p.pt[i+1])*cross(p.pt[i],c,p.pt[i+1])>0)
						{
							a = c;
							b = d;
						}
					}
				}
				newp = polygon_cross(a,b,newp);
				if(newp.n==0)
				{
					fail = 1;
					break;
				}
			}
			if(fail)
				max = mid;
			else
				min = mid;
		}
		printf("%lf\n",min);
	}
	return 0;
}