/* 给出一个凸多边形的房间,根据风水要求,把两个圆形地毯铺在房间里,不能折叠,不能切割,可以重叠。 问最多能覆盖多大空间,输出两个地毯的圆心坐标。多组解输出其中一个 将多边形的边内移R之后,半平面交区域便是可以放入圆的可行区域 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<algorithm> using namespace std; const int maxn = 105; const int maxm = 1005; const double eps = 1e-5; const double pi = acos(-1.0); struct Point{ double x,y; }; struct Line{ Point a,b; }; Point pnt[ maxn ],res[ maxm ],tp[ maxm ]; double xmult( Point op,Point sp,Point ep ){ return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x); } double dist( Point a,Point b ){ return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ); } void Get_equation( Point p1,Point p2,double &a,double &b,double &c ){ a = p2.y-p1.y; b = p1.x-p2.x; c = p2.x*p1.y-p1.x*p2.y; }//直线方程 Point Intersection( Point p1,Point p2,double a,double b,double c ){ double u = fabs( a*p1.x+b*p1.y+c ); double v = fabs( a*p2.x+b*p2.y+c ); Point tt; tt.x = (p1.x*v+p2.x*u)/(u+v); tt.y = (p1.y*v+p2.y*u)/(u+v); return tt; }//交点、按照三角比例求出交点 double GetArea( Point p[],int n ){ double sum = 0; for( int i=2;i<n;i++ ){ sum += xmult( p[1],p[i],p[i+1] ); } return -sum/2.0; }//面积,顺时针为正 void cut( double a,double b,double c,int &cnt ){ int temp = 0; for( int i=1;i<=cnt;i++ ){ if( a*res[i].x+b*res[i].y+c>-eps ){//>=0 tp[ ++temp ] = res[i]; } else{ if( a*res[i-1].x+b*res[i-1].y+c>eps ){ tp[ ++temp ] = Intersection( res[i-1],res[i],a,b,c ); } if( a*res[i+1].x+b*res[i+1].y+c>eps ){ tp[ ++temp ] = Intersection( res[i],res[i+1],a,b,c ); } } } for( int i=1;i<=temp;i++ ) res[i] = tp[i]; res[ 0 ] = res[ temp ]; res[ temp+1 ] = res[ 1 ]; cnt = temp; } void solve( int n,double r ){ if( GetArea( pnt,n)<eps ) reverse( pnt+1,pnt+1+n ); pnt[0] = pnt[n]; pnt[n+1] = pnt[1]; for( int i=0;i<=n+1;i++ ) res[ i ] = pnt[ i ]; int cnt = n; for(int i=1;i<=n;i++){ double a,b,c; Point p1,p2,p3; p1.y=pnt[i].x-pnt[i+1].x;p1.x=pnt[i+1].y-pnt[i].y; double k=r/sqrt(p1.x*p1.x+p1.y*p1.y); p1.x=k*p1.x;p1.y=p1.y*k; p2.x=p1.x+pnt[i].x;p2.y=p1.y+pnt[i].y; p3.x=p1.x+pnt[i+1].x;p3.y=p1.y+pnt[i+1].y; //移动R的部分 Get_equation( p2,p3,a,b,c ); cut(a,b,c,cnt); } double max_dis = 0; Point s,t; for( int i=1;i<=cnt;i++ ){ for( int j=1;j<=cnt;j++ ){ double d = dist( res[i],res[j] ); if(d+eps>max_dis ){ max_dis = d; s = res[i]; t = res[j]; } } } printf("%.4lf %.4lf %.4lf %.4lf\n",s.x,s.y,t.x,t.y); } int main(){ int n; double r; while( scanf("%d%lf",&n,&r)==2 ){ for( int i=1;i<=n;i++ ){ scanf("%lf%lf",&pnt[i].x,&pnt[i].y); } solve( n,r ); } return 0; }