题解 P6947【[ICPC2018 WF]Panda Preserve】

· · 题解

首先要把问题转化一下：我们不求 能覆盖所有点的最小半径，而求 覆盖每个点所需最小半径的最大值。显然这两个问题是等价的。

事实上，覆盖一个点所需最小半径，就是这个点到某个顶点的最近距离。

那么这让我们想到 Voronoi 图：关于某个点集 \mathbb S 的 V 图将平面划分成若干个部分，每个部分是一个（可能面积无限的）凸壳，所有点到 \mathbb S 中距离最近的点均相同。更多知识可以自行搜索。注意本题不需要 V 图的高效构建方法。

假如我们已经求出所有凸壳。注意任何一个 面积有限 的 不一定简单的（即，其可以有若干相离部分）多边形 到某一关键点的最远点必然位于边界（可能是其中某个部分的边界）上（可以调整，因为向边界移动必然不更劣），进而必然位于顶点（可能是某个部分的顶点）处（因为向左向右两个方向中必然有一个不更劣）。故只要顶点数可承受，我们就可以进行尝试了。

注意到并非凸壳中所有点都可以被选：其必须同时还是题面中给定的简单多边形内部的点。这意味着可选点集事实上是凸壳与给定多边形的交集。这必然是面积有限但不一定简单的多边形。

假如我们已经求出交集，则只需枚举交集的所有顶点，求出其到关键点的距离的最大值即可。

考虑交集的顶点可能有三种类型：凸壳中的顶点；给定多边形的顶点；凸壳中边与给定多边形中边的交点。

第一类可以枚举顶点然后用射线法判定是否在多边形内部解决。

射线法：自一个在简单多边形内部的顶点向外引出一条射线，其必然与该多边形的边界相交奇数次，而在外部的顶点引出的射线必然相交偶数次。

第二类不需要处理，因为多边形的顶点所需的最小半径必然是零（其自身就是集合 \mathbb S 中元素）。

第三类可以枚举简单多边形的边，用一些方法（比如说，二分/三分）在凸壳上找出交点，然后尝试更新答案。

考虑分析复杂度。计算第一类顶点需要的复杂度为 O(\text{顶点数}\times\text{射线法复杂度})。不需计算第二类顶点。计算第三类顶点需要的复杂度是 O(\text{简单多边形边数}\times\text{单次求交复杂度})。

但是，只要注意到一个性质，即 V 图中 点数和边数都是关于 |\mathbb S| 线性的，那么就可以枚举 V 图中每个顶点求射线法，再枚举 V 图中每条边和简单多边形中每条边求交点即可。这部分复杂度平方。

最后还有一个问题，就是如何求出 V 图。假如只有两个点，则考虑这两点的中垂线（垂直平分线），其左侧是到左方点更近的点集，右侧是到右方点更近的点集。对于一个点，取所有其它点求中垂线，则靠近其一侧的所有半平面的交集即为其对应的凸壳。

直接对每个点各跑一遍半平面交，复杂度平方对数。

需要注意的是，本题的瓶颈 完全在半平面交的排序。因此尽量优化你半平面交的比较。我一开始的写法一次比较傻傻地做了 4 次 atan2，然后因为常数过大在 CF 上也光荣 TLE。后来预处理出 atan2 的结果，然后就卡过去了。

代码：

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const double pi=acos(-1);
int cmp(double x){if(x>eps)return 1;if(x<-eps)return -1;return 0;}
double res;
struct Vector{
    double x,y;
    Vector(){}
    Vector(double X,double Y){x=X,y=Y;}
    friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
    friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
    friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
    friend Vector operator /(const Vector &u,const double &v){return Vector(u.x/v,u.y/v);}
    friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}
    friend double operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}
    friend bool operator ==(const Vector &u,const Vector &v){return cmp(u.x-v.x)==0&&cmp(u.y-v.y)==0;}
    double operator ~()const{return sqrt(x*x+y*y);}//the modulo of a vector
    double operator !()const{return atan2(y,x);}//the angle of a vector
    void read(){scanf("%lf%lf",&x,&y);}
    void print()const{printf("(%lf,%lf)",x,y);}
    Vector turn(){return Vector(y,-x);}
    friend bool operator<(const Vector&u,const Vector&v){
        if(cmp(u.x-v.x)==0)return cmp(u.y-v.y)==-1;
        return cmp(u.x-v.x)==-1;
    }
}p[2010],q[2010];
typedef Vector Point;
struct Line{
    Point x,y;
    Vector z;double ang;
    Line(){}
    Line(Point X,Point Y){x=X,y=Y,z=Y-X,ang=!z;}
    friend bool operator<(const Line&u,const Line&v){
        if(cmp(u.ang-v.ang))return u.ang<v.ang;
        return cmp(u.z&(v.y-u.x))==-1;
    }
    friend bool operator/(const Line&u,const Line&v){return cmp(u.z&v.z)==0;}
    friend bool operator|(const Line&u,const Line&v){return cmp(u.ang-v.ang)==0;}
    friend bool operator&(const Line&u,const Point&v){return cmp((v-u.x)&u.z)!=1;}
    friend bool operator%(const Line&u,const Point&v){return cmp((u.x-v)|(u.y-v))!=1;}
    friend Point operator&(const Line&u,const Line&v){return u.x+u.z*((v.z&(u.x-v.x))/(u.z&v.z));}
}l[2010],r[2010];
typedef Line Segment;
int n,L,R,m;
set<Point>st;
bool inside(Point P){
    if(st.find(P)!=st.end())return false;
    st.insert(P);
    static default_random_engine rnd(17680321);
    static uniform_real_distribution<double>urd(-pi,pi);
    while(true){
        double ang=urd(rnd);
        Point Q(P.x+cos(ang),P.y+sin(ang));
        Line X(P,Q);
        int num=0;
        for(int i=0;i<n;i++){
            Point A=p[i],B=p[(i+1)%n];
            Line Y(A,B);
            Point C=Y&X;
            if(C==B||C==A){num=-1;break;}
            if(!(Y%C)||(Segment(Q,C)%P&&!(P==C)))continue;
            num++;
        }
        if(num!=-1)return num&1;
    }
}
void solve(int _){
    m=0;
    for(int i=0;i<n;i++)if(i!=_){
        Point P=(p[i]+p[_])/2;
        Point Q=P+(p[_]-p[i]).turn();
        // P.print(),Q.print();puts("");
        l[m++]=Line(P,Q);
    }
    l[m++]=Line(Point(-2e4,-2e4),Point(2e4,-2e4));
    l[m++]=Line(Point(2e4,-2e4),Point(2e4,2e4));
    l[m++]=Line(Point(2e4,2e4),Point(-2e4,2e4));
    l[m++]=Line(Point(-2e4,2e4),Point(-2e4,-2e4));
    sort(l,l+m),r[L=R=0]=l[0];
    for(int i=1;;i++){
        while(i<m&&l[i]|l[i-1])i++;
        if(i==m)break;
        if(L<R&&((r[L]/r[L+1])||(r[R]/r[R-1])))return;
        while(L<R&&!(l[i]&q[R-1]))R--;
        while(L<R&&!(l[i]&q[L]))L++;
        r[++R]=l[i];if(L<R)q[R-1]=r[R]&r[R-1];
    }
    while(L<R&&!(r[L]&q[R-1]))R--;
    while(L<R&&!(r[R]&q[L]))L++;
    if(R-L<=1)return;
    q[R]=r[L]&r[R];
    // printf("%d:\n",_);
    // for(int i=L;i<=R;i++)q[i].print();puts("");
    for(int i=L;i<=R;i++)if(inside(q[i]))res=max(res,~(q[i]-p[_]));
    for(int i=L;i<=R;i++)for(int j=0;j<n;j++){
        Segment s(p[j],p[(j+1)%n]),t(q[i],q[i==R?L:i+1]);
        if(s/t)continue;
        Point P=s&t;
        if(s%P&&t%P)res=max(res,~(P-p[_]));
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)p[i].read();
    for(int i=0;i<n;i++)solve(i);
    printf("%lf\n",res);
    return 0;
}