poj3384 Feng Shui 半平面交

//题目链接：http://poj.org/problem?id=3384
//题意:用两个圆去覆盖一个多边形，求最多覆盖面积时两个圆的圆心（按一定顺序）。
//多边形向内推进r求半平面交 + 最远点对

//这里的数据不够大，可以用暴力求最远点对 94ms AC，代码如下：

#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-8
//using namespace std;
const int MAXN=202;
struct point{double x,y;};
point points[MAXN],p[MAXN],q[MAXN];
int n;
double r;
bool zero(double x)
{
	return x>0? x<eps:x>-eps;
}
double xmult(point p1,point p2,point p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int same_side(point p1,point p2,point l1,point l2)
{
	return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
point intersection(point p1,point p2,point p3,point p4)
{
	point ret=p1;
	double t=((p1.x-p3.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p3.y))
		/((p1.x-p2.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p2.y));
	ret.x+=t*(p2.x-p1.x);
	ret.y+=t*(p2.y-p1.y);
	return ret;
}
void polygon_cut(int &n,point *p,point l1,point l2,point side)
{
	point pp[1000];
	int m=0,i;
	for(i=0;i<n;i++)
	{
		if(same_side(p[i],side,l1,l2))
			pp[m++]=p[i];
		if(!same_side(p[i],p[(i+1)%n],l1,l2)
			&&!(zero(xmult(p[i],l1,l2))
			&&zero(xmult(p[(i+1)%n],l1,l2))))
			pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2);
	}
	n=0;
	for(i=0;i<m;i++)
		if(!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y))
			p[n++]=pp[i];
		if(zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y))
			n--;//
		// if(n<3)n=0;
}
double distance(point p1,point p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void slove(double dis,int &m)
{
	int i;
	for(i=0;i<n;i++)p[i]=points[i];
	for(i=0;i<n;i++)
	{
		point side;
		point s=points[i],e=points[(i+1)%n];
		double xx=s.x-e.x,yy=s.y-e.y;
		double dd=sqrt(xx*xx+yy*yy);
		s.x+=dis*(-yy)/dd;
		s.y+=dis*(xx)/dd;
		e.x+=dis*(-yy)/dd;
		e.y+=dis*(xx)/dd;
		side.x=s.x-yy;
		side.y=s.y+xx;
		polygon_cut(m,p,s,e,side);
	}
}
int main()
{
	
	while(scanf("%d%lf",&n,&r)!=EOF)
	{
		int i,j;
		for(i=0;i<n;i++)
			scanf("%lf%lf",&points[i].x,&points[i].y);
		int m=n;
		slove(r,m);
		// for(i=0;i<m;i++)printf("%lf,%lf\n",p[i].x,p[i].y);
		double dis=0;
		int s=0,e=0;
		for(i=0;i<m;i++)
		{
			for(j=0;j<m;j++)
				if(i!=j)
				{
					double temp=distance(p[i],p[j]);
					if(temp-dis>eps)
					{
						dis=temp;
						s=i;e=j;
					}
				}
		}
		if(p[s].x-p[e].x>eps||zero(p[s].x-p[e].x)&&p[s].y>-p[e].y>eps)
		{
			point tt=p[s];
			p[s]=p[e];
			p[e]=tt;
		}
		
		printf("%.10lf %.10lf %.10lf %.10lf\n",p[s].x,p[s].y,p[e].x,p[e].y);
	}
	return 0;
}