题解 UVA1396 【Most Distant Point from the Sea】

2019-02-20 19:34:19


题解:

本题求的是多边形内部任意一点到边的最小距离的最大值。

做这道题的时候只是觉得这个题有点像二分的模型,并且有合理的二分方式。上面那句话是我写题解的时候口胡出来的,由此可以知道,很多的二分题都会在体现在题意中,另见NOIP 2018 赛道修建 题解

因为点 $\left\{P_i\right\}$ 是逆时针给出来的,所以半平面交的可行域是向量 $\overrightarrow{P_iP_{i+1}}(i<n),\overrightarrow{P_nP_1}$ (下同) 的左侧。

二分是直接二分答案,因此考虑把每个向量向左平移 $mid$ 个单位。平移这一操作很好完成,首先把向量逆时针旋转 $90^\circ$ ,然后放缩到原来长度 $k=|P_iP_{i+1}|$ 的 $\frac{mid}k$ 倍,得到向量 $\overrightarrow v$ 令 $P_i$ 和 $P_{i+1}$ 同时加上 $\overrightarrow v$ 即可。然后再做半平面交,bool check()函数的返回值为“面积大于 $0$ 为真”。

最后需要用long double输出。(不知道为什么double被卡了……)

Code:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db long double
#define eps 1e-10
struct pnt
{
    db x,y;
    pnt(db x,db y)
    {
        this->x=x;
        this->y=y;
    }
    pnt(){}
    friend pnt operator +(pnt a,pnt b)
    {return pnt(a.x+b.x,a.y+b.y);}
    friend pnt operator -(pnt a,pnt b)
    {return pnt(a.x-b.x,a.y-b.y);}
    friend db operator *(pnt a,pnt b)
    {return a.x*b.y-a.y*b.x;}
    pnt times(db k)
    {return pnt(x*k,y*k);}
    db len()
    {return sqrt(x*x+y*y);}
}p[105],t[105];
struct seg
{
    pnt a,b;
    db d;
    seg(pnt a,pnt b)
    {
        this->a=a;
        this->b=b;
        d=atan2((b-a).y,(b-a).x);
    }
    seg(){}
    friend bool operator <(seg x,seg y)
    {
        if(fabs(x.d-y.d)>eps)
            return x.d<y.d;
        return (y.a-x.a)*(y.b-x.a)>eps;
    }
    friend bool operator !=(seg x,seg y)
    {return fabs(x.d-y.d)>eps;}
}s[105],f[105],q[105];
pnt its(seg x,seg y)
{
    db u=(y.a-x.a)*(y.b-x.a);
    db d=u+(y.b-x.b)*(y.a-x.b);
    return x.a+(x.b-x.a).times(u/d);
}
int n;
bool check(db k)
{
    for(int i=1;i<=n;++i)
    {
        db R=(s[i].b-s[i].a).len();
        pnt v(-(s[i].b-s[i].a).y,(s[i].b-s[i].a).x);
        v=v.times(k/R);
        f[i]=seg(s[i].a+v,s[i].b+v);
    }
    std::sort(f+1,f+1+n);
    int l=0,r=0;
    for(int i=1;i<=n;++i)
        if(f[i]!=f[i-1])
        {
            while(r-l>1&&(f[i].b-t[r])*(f[i].a-t[r])>-eps)
                --r;
            while(r-l>1&&(f[i].b-t[l+2])*(f[i].a-t[l+2])>-eps)
                ++l;
            q[++r]=f[i];
            if(r-l>1)
                t[r]=its(q[r],q[r-1]);
        }
    while(r-l>1&&(q[l+1].b-t[r])*(q[l+1].a-t[r])>eps)
        --r;
    t[l+1]=its(q[l+1],q[r]);
    db sum=t[r]*t[l+1];
    for(int i=l+1;i<r;++i)
        sum+=t[i]*t[i+1];
    return sum>eps;
}
int main()
{
    scanf("%d",&n);
    f[0].d=233;
    while(n)
    {
        for(int i=1;i<=n;++i)
        {
            scanf("%Lf%Lf",&p[i].x,&p[i].y);
            if(i>1)
                s[i]=seg(p[i-1],p[i]);
        }
        1[s]=seg(p[n],p[1]);
        db l=0,r=5000,mid;
        while(r-l>1e-9)
        {
            mid=(l+r)/2;
            if(check(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%.8Lf\n",l);
        scanf("%d",&n);
    }
    return 0;
}