題目描述：

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; } View Code

?

轉載于:https://www.cnblogs.com/LiGuanlin1124/p/10825146.html

總結

以上是生活随笔為你收集整理的bzoj5183 [Baltic2016]Park的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。