题意分析

本题要求在一个给定的凸多边形房间内放置两个半径为$r$的圆形地毯，使得它们覆盖的总面积最大。地毯可以重叠，但不能裁剪或折叠，且必须完全位于房间内。

解题思路

1. 问题转化：

   • 找到凸多边形的"核"，即所有顶点向内收缩$r$后的区域。这个区域内的任意点作为圆心都能保证圆完全在多边形内。
   • 在核区域内找到两个点，使得它们之间的距离最大，这两个点即为两个圆的圆心。

2. 半平面交算法：

   • 使用半平面交算法计算凸多边形的核。对于每条边，将其向内平移$r$的距离，得到新的边，所有这些新边的交集即为核。
   • 半平面交的实现采用增量法，逐步切割多边形，保留符合条件的区域。

3. 最远点对：

   • 在得到的核区域中，枚举所有点对，找到距离最大的点对，即为两个圆的圆心位置。

代码解释

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
const double EPS=1e-11;  // 浮点数精度控制
const int NUM=1510;
 
// 判断浮点数符号
int DB (double x)
{
    if (x>EPS)
        return 1;
    if (x<-EPS)
        return -1;
    return 0;
}
 
// 点结构
struct Point
{
    double x,y;
 
    Point(){}
    Point(double _x,double _y)
    {
        x=_x;
        y=_y;
    }
 
    void get ()
    {
        scanf("%lf%lf",&x,&y);
    }
 
    void Out ()
    {
        printf("%.4lf %.4lf",x,y);
    }
}points[NUM],p[NUM],q[NUM];  // points存储原始多边形，p存储当前多边形，q用于临时存储
 
int n,r;  // n为顶点数，r为圆半径
int cCnt,curCnt;  // cCnt为当前多边形顶点数，curCnt为切割后的临时顶点数
 
// 根据两点求直线方程ax+by+c=0
void getline (Point x,Point y,double &a,double &b,double &c)
{
    a = y.y - x.y;
    b = x.x - y.x;
    c = y.x * x.y - x.x * y.y;
}
 
// 求点x,y与直线ax+by+c=0的交点
Point intersect (Point x,Point y,double a,double b,double c)
{
    double u = fabs(a * x.x + b * x.y + c);
    double v = fabs(a * y.x + b * y.y + c);
    return Point( (x.x * v + y.x * u) / (u + v) , (x.y * v + y.y * u) / (u + v) );
}
 
// 用直线ax+by+c=0切割多边形
void cut (double a,double b ,double c)
{
    int i;
    curCnt = 0;
    for (i=1;i<=cCnt;i++)
    {
        if (DB(a*p[i].x + b*p[i].y + c) >= 0)  // 当前点在直线右侧（或线上）
            q[++curCnt] = p[i];
        else  // 当前点在直线左侧
        {
            if (DB(a*p[i-1].x + b*p[i-1].y + c) > 0)  // 前一点在右侧，求交点
                q[++curCnt] = intersect(p[i],p[i-1],a,b,c);
            if (DB(a*p[i+1].x + b*p[i+1].y + c) > 0)  // 后一点在右侧，求交点
                q[++curCnt] = intersect(p[i],p[i+1],a,b,c);
        }
    }
    for (i=1;i<=curCnt;i++)
        p[i] = q[i];
    p[curCnt+1] = q[1];
    p[0] = p[curCnt];
    cCnt = curCnt;
}
 
// 规整化方向（题目中未使用，保留）
void GuiZhengHua ()
{
    for (int i=1;i<(n+1)/2;i++)
        swap(points[i], points[n-i]);
}
 
// 初始化多边形
void initial ()
{
    for (int i=1;i<=n;i++)
        p[i] = points[i];  
    p[n+1] = p[1];
    p[0] = p[n];
    cCnt = n;
}
 
// 计算两点距离
double dis (Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
 
// 处理主函数
void Deal ()
{
    int i,j;
    
    // 初始化多边形
    initial ();
    
    // 对每条边进行向内平移r的操作，并切割多边形
    for (i=1;i<=n;i++)
    {
        Point ta, tb, tt; 
        tt.x = points[i+1].y - points[i].y;  // 计算法向量
        tt.y = points[i].x - points[i+1].x; 
        double k = r / sqrt(tt.x * tt.x + tt.y * tt.y);  // 计算缩放因子
        tt.x = tt.x * k;  // 缩放法向量
        tt.y = tt.y * k; 
        ta.x = points[i].x + tt.x;  // 计算平移后的点
        ta.y = points[i].y + tt.y; 
        tb.x = points[i+1].x + tt.x; 
        tb.y = points[i+1].y + tt.y; 
        double a,b,c; 
        getline(ta,tb,a,b,c);  // 求平移后的直线方程
        cut(a,b,c);  // 用新直线切割多边形
    }
    
    // 在得到的核区域中找到最远点对
    Point ansa,ansb;
    double dmax=-1;
    for (i=1;i<=cCnt;i++)
        for (j=1;j<=cCnt;j++)  // 枚举所有点对
            if (dis(p[i],p[j])>dmax)
            {
                dmax=dis(p[i],p[j]);
                ansa=p[i];
                ansb=p[j];
            }
    printf("%.4lf %.4lf %.4lf %.4lf\n",ansa.x,ansa.y,ansb.x,ansb.y);
} 
 
int main ()
{
    while (~scanf("%d%d",&n,&r))
    {
        for (int i=1;i<=n;i++)
            points[i].get();
        points[0]=points[n];
        points[n+1] = points[1];
        Deal ();
    }
    return 0;
}

关键步骤解析

1. 半平面交计算核区域：

   • 对于每条边，计算其向内平移$r$后的新边。
   • 使用新边切割当前多边形，保留符合条件的区域。
   • 所有边处理完后，得到的多边形即为核区域。

2. 最远点对查找：

   • 在核区域的所有顶点中枚举所有点对，计算距离。
   • 记录最大距离的点对，即为两个圆的圆心。

3. 浮点数精度处理：

   • 使用DB函数判断浮点数符号，处理精度误差。
   • 设置合适的EPS值（1e-11）确保计算准确性。

复杂度分析

• 时间复杂度：$O(n^2)$，主要来自半平面交的$O(n)$和枚举最远点对的$O(n^2)$。
• 空间复杂度：$O(n)$，用于存储多边形顶点。

该算法通过半平面交和枚举最远点对，高效地解决了在凸多边形内放置两个圆的问题，确保了覆盖面积最大。