3171662_wa.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;
}

double dis(point a,point b)
{
	return hypot(a.x-b.x,a.y-b.y);
}

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

	scanf("%d%lf",&p.n,&r);
	minx = miny = 10000;
	for(i = 0; i < p.n; 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];
	newp = p;
	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 += r;
				b.x += r;
			}
			else
			{
				a.x -= r;
				b.x -= r;
			}
		}
		else
		{
			if(a.y==b.y)
			{
				if(a.y==miny)
				{
					a.y += r;
					b.y += r;
				}
				else
				{
					a.y -= r;
					b.y -= r;
				}
			}
			else
			{
				alpha = atan((b.y-a.y)/(b.x-a.x));
				deltax = r/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);
	}
	max = -1;
	for(i = 0; i < newp.n; i++)
	{
		for(j = i+1; j < newp.n; j++)
		{
			double tmp = dis(newp.pt[i],newp.pt[j]);
			if(tmp > max)
			{
				max = tmp;
				a = newp.pt[i];
				b = newp.pt[j];
			}
		}
	}
	printf("%lf %lf %lf %lf\n",a.x,a.y,b.x,b.y);
	return 0;
}