link
[P4675 BalticOI 2016 day1
solve
前段时间做了一道对偶图的题,让我有了一个启发
对于两个点能不能到达,可以重新建图后判断是否存在一条边把图形切成两半
这道题也是这个想法
将四个边界看成四个点,和障碍点的距离就是距离-半径
我们离线处理,从小到大处理答案,因为小的不能过大的肯定不能过
最后用并查集判断四边是否联通就好了
code
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-4;
int len_edge,N,M,Max_x,Max_y;
int fa[2005];
struct Obs{
int x,y;
double r;
double operator -(Obs B){return sqrt(((double)this->x-B.x)*(this->x-B.x)+((double)this->y-B.y)*(this->y-B.y))-this->r-B.r;}
}ob[2010];
struct que{
int e,ans[5],id,r;
bool operator <(const que B)const {return r<B.r;}
}q[1000005];
struct edge{
int id_x,id_y;
double l;
bool operator <(const edge B)const {return l<B.l;}
}E[2010*2010];
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
bool cmp(que A,que B){return A.id<B.id;}
int main(){
freopen("P4675.in","r",stdin);
freopen("P4675.out","w",stdout);
N=read();M=read();Max_x=read();Max_y=read();
for(int i=1;i<=N;i++) ob[i].x=read(),ob[i].y=read(),ob[i].r=read();
for(int i=1;i<=M;i++) q[i].r=read(),q[i].e=read(),q[i].id=i;
for(int i=1;i<=N;i++){
E[++len_edge]=(edge){i,N+1,double(ob[i].x-ob[i].r)};
E[++len_edge]=(edge){i,N+2,double(ob[i].y-ob[i].r)};
E[++len_edge]=(edge){i,N+3,double(Max_x-ob[i].x-ob[i].r)};
E[++len_edge]=(edge){i,N+4,double(Max_y-ob[i].y-ob[i].r)};
for(int j=i+1;j<=N;j++)
E[++len_edge]=(edge){i,j,ob[i]-ob[j]};
}
int now=1;sort(E+1,E+1+len_edge);sort(q+1,q+1+M);
for(int i=1;i<=N+4;i++) fa[i]=i;
for(int i=1;i<=M;i++){
// if(q[i].r==15980326){
// printf("
");
// }
while(now<=len_edge&&E[now].l+eps<(q[i].r*2)){
int fx=get(E[now].id_x),fy=get(E[now].id_y);if(fx!=fy) fa[fx]=fy;
now++;
}
int Le=get(N+1),Dn=get(N+2),Ri=get(N+3),Up=get(N+4);
q[i].ans[1]=q[i].ans[2]=q[i].ans[3]=q[i].ans[4]=1;
if(q[i].e==1){
if(Le==Dn){q[i].ans[2]=q[i].ans[3]=q[i].ans[4]=0;}
else {
if(Le==Ri) q[i].ans[3]=q[i].ans[4]=0;
if(Up==Dn) q[i].ans[2]=q[i].ans[3]=0;
Le==Dn&&q[i].ans[1]=0;
if(Ri==Dn) q[i].ans[2]=0;
if(Up==Ri) q[i].ans[3]=0;
if(Up==Le) q[i].ans[4]=0;
}
}
else if(q[i].e==2){
if(Ri==Dn) q[i].ans[1]=q[i].ans[3]=q[i].ans[4]=0;
else {
if(Le==Ri) q[i].ans[3]=q[i].ans[4]=0;
if(Up==Dn) q[i].ans[1]=q[i].ans[4]=0;
if(Le==Dn) q[i].ans[1]=0;
if(Ri==Dn) q[i].ans[2]=0;
if(Up==Ri) q[i].ans[3]=0;
if(Up==Le) q[i].ans[4]=0;
}
}
else if(q[i].e==3){
if(Up==Ri) q[i].ans[1]=q[i].ans[2]=q[i].ans[4]=0;
else {
if(Le==Ri) q[i].ans[1]=q[i].ans[2]=0;
if(Up==Dn) q[i].ans[1]=q[i].ans[4]=0;
if(Le==Dn) q[i].ans[1]=0;
if(Ri==Dn) q[i].ans[2]=0;
if(Up==Ri) q[i].ans[3]=0;
if(Up==Le) q[i].ans[4]=0;
}
}
else if(q[i].e==4){
if(Up==Le) q[i].ans[1]=q[i].ans[2]=q[i].ans[3]=0;
else {
if(Le==Ri) q[i].ans[1]=q[i].ans[2]=0;
if(Up==Dn) q[i].ans[2]=q[i].ans[3]=0;
if(Le==Dn) q[i].ans[1]=0;
if(Ri==Dn) q[i].ans[2]=0;
if(Up==Ri) q[i].ans[3]=0;
if(Up==Le) q[i].ans[4]=0;
}
}
q[i].ans[q[i].e]=1;
}
sort(q+1,q+1+M,cmp);
for(int i=1;i<=M;i++){
for(int j=1;j<=4;j++) if(q[i].ans[j]) putchar(j+'0');
putchar('
');
}
return 0;
}