[POJ 3384] | Eurce's Blog

半平面交

题意：给出一个凸多边形描述，问如何在凸多边形内放两个半径都为r的圆，使两圆覆盖区域并集的面积最大。两圆可以重叠，但重叠部分面积不累加。圆不能超出凸多边形的边界。题目保证有解，若有多解，输出任意一组。

根据题意，目标要使两圆重叠区域最小。很容易推出可行的圆心区域是原凸多边形各边向内“塌缩”r后围成的新多边形。那么，在这个新多边形内，找出距离最远的两个端点即可。

实现起来也不太难，由于数据规模不大（n最多100），直接用了O(n^3)的方法。具体做法是，首先算出各边沿斜率直角方向向内平移r后的新方程，然后求各直线间的交点。由于塌缩后，某些直线会完全位于有效区域之外，因此，对于这O(n^2)个交点，需要再用n条新直线方程判是否有效。最后，在剩余的交点中找出距离最远的两个即可。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8

int n,mxi,mxj;
double r,x[10000],y[10000],mx;

struct E
{
    double x1,y1,x2,y2;
    double a,b,c;
}e[100];

void init()
{
    int i,j;
    double ang,x1,y1,x2,y2;
    mx=-1;
    for(i=0;i<n;i++)
        scanf("%lf%lf",x+i,y+i);
    for(i=0;i<n;i++)
    {
        j=(i+1)%n;
        x1=x[i]; y1=y[i]; x2=x[j]; y2=y[j];
        ang=atan2(x1-x2,y2-y1);
        x1+=r*cos(ang); y1+=r*sin(ang);
        x2+=r*cos(ang); y2+=r*sin(ang);
        e[i].x1=x1; e[i].y1=y1; e[i].x2=x2; e[i].y2=y2;
        e[i].a=y1-y2;
        e[i].b=x2-x1;
        e[i].c=(y2-y1)*x1-(x2-x1)*y1;
        if(abs(e[i].a)<eps)
        {
            e[i].a=0;
            e[i].c/=e[i].b;
            e[i].b=1;
        }
        else
        {
            e[i].b/=e[i].a;
            e[i].c/=e[i].a;
            e[i].a=1;
        }
    }
}

double crs(double x0,double y0,double x1,double y1,
        double x2,double y2)
{
    x1-=x0; y1-=y0; x2-=x0; y2-=y0;
    return x1*y2-x2*y1;
}

void solve()
{
    int i,j,k,l;
    double a1,b1,c1,a2,b2,c2,d;
    for(i=k=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            a1=e[i].a; b1=e[i].b; c1=e[i].c;
            a2=e[j].a; b2=e[j].b; c2=e[j].c;
            if(abs(a1-a2)<eps&&abs(b1-b2)<eps)
                continue;
            if(abs(a1)<eps)
            {
                y[k]=-c1/b1;
                x[k]=(-c2-b2*y[k])/a2;
            }
            else
            {
                y[k]=(a2*c1-a1*c2)/(a1*b2-a2*b1);
                x[k]=(-c1-b1*y[k])/a1;
            }
            k++;
        }
    }
    for(i=l=0;i<k;i++)
    {
        for(j=0;j<n;j++)
        {
            if(crs(e[j].x1,e[j].y1,x[i],y[i],e[j].x2,e[j].y2)<-eps)
                break;
        }
        if(j==n)
        {
            x[l]=x[i];
            y[l]=y[i];
            l++;
        }
    }
    for(i=0;i<l-1;i++)
    {
        for(j=i+1;j<l;j++)
        {
            d=pow(x[i]-x[j],2)+pow(y[i]-y[j],2);
            if(d>mx)
            {
                mx=d;
                mxi=i;
                mxj=j;
            }
        }
    }
    printf("%.4f %.4f %.4f %.4f\n",x[mxi],y[mxi],x[mxj],y[mxj]);
}

int main()
{
    while(~scanf("%d%lf",&n,&r))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n,mxi,mxj;

double r,x[10000],y[10000],mx;

struct E

{

double x1,y1,x2,y2;

double a,b,c;

}e[100];

void init()

{

int i,j;

double ang,x1,y1,x2,y2;

mx=-1;

for(i=0;i<n;i++)

scanf("%lf%lf",x+i,y+i);

for(i=0;i<n;i++)

{

j=(i+1)%n;

x1=x[i]; y1=y[i]; x2=x[j]; y2=y[j];

ang=atan2(x1-x2,y2-y1);

x1+=r*cos(ang); y1+=r*sin(ang);

x2+=r*cos(ang); y2+=r*sin(ang);

e[i].x1=x1; e[i].y1=y1; e[i].x2=x2; e[i].y2=y2;

e[i].a=y1-y2;

e[i].b=x2-x1;

e[i].c=(y2-y1)*x1-(x2-x1)*y1;

if(abs(e[i].a)<eps)

{

e[i].a=0;

e[i].c/=e[i].b;

e[i].b=1;

}

else

{

e[i].b/=e[i].a;

e[i].c/=e[i].a;

e[i].a=1;

}

double crs(double x0,double y0,double x1,double y1,

double x2,double y2)

{

x1-=x0; y1-=y0; x2-=x0; y2-=y0;

return x1*y2-x2*y1;

}

void solve()

{

int i,j,k,l;

double a1,b1,c1,a2,b2,c2,d;

for(i=k=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

a1=e[i].a; b1=e[i].b; c1=e[i].c;

a2=e[j].a; b2=e[j].b; c2=e[j].c;

if(abs(a1-a2)<eps&&abs(b1-b2)<eps)

continue;

if(abs(a1)<eps)

{

y[k]=-c1/b1;

x[k]=(-c2-b2*y[k])/a2;

}

else

{

y[k]=(a2*c1-a1*c2)/(a1*b2-a2*b1);

x[k]=(-c1-b1*y[k])/a1;

}

k++;

}

for(i=l=0;i<k;i++)

{

for(j=0;j<n;j++)

{

if(crs(e[j].x1,e[j].y1,x[i],y[i],e[j].x2,e[j].y2)<-eps)

break;

}

if(j==n)

{

x[l]=x[i];

y[l]=y[i];

l++;

}

for(i=0;i<l-1;i++)

{

for(j=i+1;j<l;j++)

{

d=pow(x[i]-x[j],2)+pow(y[i]-y[j],2);

if(d>mx)

{

mx=d;

mxi=i;

mxj=j;

}

printf("%.4f %.4f %.4f %.4f\n",x[mxi],y[mxi],x[mxj],y[mxj]);

}

int main()

{

while(~scanf("%d%lf",&n,&r))

{

init();

solve();

}

return 0;

}