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;}