bzoj5183 [Baltic2016]Park

题目描述：

bz

luogu

题解：

把坐标系看反了持续$WA$系列。

对偶图+并查集维护。

先处理出树对树、树对墙的空隙，然后把人和空隙按从小到大排序。

用并查集维护四面墙之间是否能互相隔断。

代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2550;
const int M = 100050;
const double eps = 1e-6;
template<typename T>
inline void read(T&x)
{
    T f = 1,c = 0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    x = f*c;
}
int n,m,X[2],Y[2],ff[N];
double W,H;
int findff(int x){return x==ff[x]?x:ff[x]=findff(ff[x]);}
struct Tree
{
    double x,y,r;
    void rd(){scanf("%lf%lf%lf",&x,&y,&r);}
}t[N];
double sqr(double k){return k*k;}
double dis(int i,int j){return sqrt(sqr(t[i].x-t[j].x)+sqr(t[i].y-t[j].y));}
int tot;
struct Hole
{
    double k;
    int x,y;
    Hole(){}
    Hole(double k,int x,int y):k(k),x(x),y(y){}
}h[N*N];
bool cmp(Hole a,Hole b){return a.k<b.k;}
int ans[M];
struct Peo
{
    double r;
    int c,id;
    void rd(int i){scanf("%lf",&r),r*=2;read(c),c--;id=i;}
}p[M];
bool vmp(Peo a,Peo b){return a.r<b.r;}
void merge(int x,int y)
{
    x = findff(x),y = findff(y);
    if(x!=y)ff[x]=y;
}
bool cX(){return findff(X[0])==findff(X[1]);}
bool cY(){return findff(Y[0])==findff(Y[1]);}
int Xi[4]={0,0,1,1},Yi[4]={0,1,1,0};
bool cC(int cn){return findff(X[Xi[cn]])==findff(Y[Yi[cn]]);}
void ot(int x)
{
    for(int i=0;i<4;i++)if(ans[x]&(1<<i))
        putchar('1'+i);
    puts("");
}
int main()
{
    read(n),read(m);
    scanf("%lf%lf",&W,&H);
    X[0] = n+1,X[1] = n+2,Y[0] = n+3,Y[1] = n+4;
    for(int i=1;i<=n+4;i++)ff[i]=i;
    for(int i=1;i<=n;i++)
    {
        t[i].rd();
        h[++tot] = Hole(t[i].x-t[i].r,i,Y[0]);
        h[++tot] = Hole(t[i].y-t[i].r,i,X[0]);
        h[++tot] = Hole(W-t[i].x-t[i].r,i,Y[1]);
        h[++tot] = Hole(H-t[i].y-t[i].r,i,X[1]);
    }
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
        h[++tot] = Hole(dis(i,j)-t[i].r-t[j].r,i,j);
    for(int i=1;i<=m;i++)p[i].rd(i);
    sort(p+1,p+1+m,vmp),sort(h+1,h+1+tot,cmp);
    for(int i=1,j=1;i<=m;i++)
    {
        while(h[j].k+eps<p[i].r&&j<=tot)
            merge(h[j].x,h[j].y),j++;
        bool cx = cX(),cy = cY();int cc = p[i].c;
        if(cC(cc)){ans[p[i].id]=(1<<cc);continue;}
        if(cx&&cy)ans[p[i].id]=(1<<cc);
        else if(cx&&!cy)ans[p[i].id]=((1<<cc)|(1<<(cc^3)));
        else if(!cx&&cy)ans[p[i].id]=((1<<cc)|(1<<(cc^1)));
        else ans[p[i].id]=15;
        for(int cn=0;cn<4;cn++)
            if(cC(cn)&&(ans[p[i].id]&(1<<cn)))ans[p[i].id]^=(1<<cn);
    }
    for(int i=1;i<=m;i++)ot(i);
    return 0;
}