POJ 3384 放地毯【半平面交】

时间：2023-11-24 12:09:08

<题目链接>

题目大意：

给出一个凸多边形的房间，根据风水要求，把两个圆形地毯铺在房间里，不能折叠，不能切割，可以重叠。问最多能覆盖多大空间，输出两个地毯的圆心坐标。多组解输出其中一个，题目保证至少可以放入一个圆。

解题分析：

因为放置的圆不能超出多边形的边界，所以先将该凸多边形的各个边长向内平移 r 的距离，然后对这些平移后的直线用半平面交去切割原多边形，切割后得到的区域就是两圆圆心所在的区域，然后遍历这个切割后的多边形的各个顶点，距离最远的两个顶点就是这两圆的圆心。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

#define N 10005

const double pi=acos(-1.0);

const double inf=1e9;

const double eps=1e-;

int dcmp(double x)

{

    if (x<=eps&&x>=-eps) return ;

    return (x>)?:-;

}

struct Vector

{

    double x,y;

    Vector(double X=,double Y=)

    {

        x=X,y=Y;

    }

};

typedef Vector Point;

Vector operator + (Vector a,Vector b) {return Vector(a.x+b.x,a.y+b.y);}

Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);}

Vector operator * (Vector a,double p) {return Vector(a.x*p,a.y*p);}

int n,cnt,ncnt,ansi,ansj;

double x,y,r,ans;

Point p[N],poly[N],npoly[N];

double Dot(Vector a,Vector b)

{

    return a.x*b.x+a.y*b.y;

}

double Cross(Vector a,Vector b)

{

    return a.x*b.y-a.y*b.x;

}

double Len(Vector a)

{

    return sqrt(Dot(a,a));

}

Vector rotate(Vector a,double rad)

{

    return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));

}

bool insLS(Point A,Point B,Point C,Point D)

{

    Vector v=B-A,w=C-A,u=D-A;

    return dcmp(Cross(v,w))!=dcmp(Cross(v,u));

}

Point GLI(Point P,Vector v,Point Q,Vector w)

{

    Vector u=P-Q;

    double t=Cross(w,u)/Cross(v,w);

    return P+v*t;

}

void init()

{

    cnt=;

    poly[++cnt]=Point(inf,inf);

    poly[++cnt]=Point(inf,-inf);

    poly[++cnt]=Point(-inf,-inf);

    poly[++cnt]=Point(-inf,inf);

}

void halfp(Point A,Point B)

{

    ncnt=;

    Point C,D;

    for (int i=;i<=cnt;++i)

    {

        C=poly[i%cnt+];

        D=poly[(i+)%cnt+];

        if (dcmp(Cross(B-A,C-A))<=)

            npoly[++ncnt]=C;

        if (insLS(A,B,C,D))

            npoly[++ncnt]=GLI(A,B-A,C,D-C);

    }

    cnt=ncnt;

    for (int i=;i<=cnt;++i)

        poly[i]=npoly[i];

}

int main()

{

    scanf("%d%lf",&n,&r);

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

    {

        scanf("%lf%lf",&x,&y);

        p[i]=Point(x,y);

    }

    init();

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

    {

        Point A=p[i%n+];

        Point B=p[(i+)%n+];

        Vector v=B-A;

        Vector w=rotate(v,-pi/2.0);

        w=w*(r/Len(w));

        Point C=A+w;

        Point D=C+v;

        halfp(C,D);

    }

    ansi=ansj=;

    for (int i=;i<=cnt;++i)

        for (int j=i+;j<=cnt;++j)

        {

            double dis=Len(poly[i]-poly[j]);

            if (dcmp(dis-ans)>)

            {

                ans=dis;

                ansi=i,ansj=j;

            }

        }

    printf("%.4lf %.4lf %.4lf %.4lf\n",poly[ansi].x,poly[ansi].y,poly[ansj].x,poly[ansj].y);

}

2018-08-03

相关文章