本地、本校OJ(linux)都能通过大样例,洛谷一直RE,代码有什么问题吗?
#include<bits/stdc++.h>
#define LL long long
#define DB double
const int maxn=4005,maxm=2e5+5,maxe=3e6+5;
int n,m,w,h;
struct obj{
int x,y,r,id;
}a[maxn],a0[maxn],a1[maxn];
bool cmp0(obj i,obj j){
return i.x<j.x;
}
bool cmp1(obj i,obj j){
return i.y<j.y;
}
struct data{
int x,y,r;
bool operator <(data b)const{return r<b.r;}
}e[maxe+maxn*4];
struct hum{
int id,e,r;
bool operator <(hum b)const{return r<b.r;}
}b[maxm];
int tot;
int cnt;
DB sqr(int x){
return (DB)x*x;
}
DB dis(int i,int j){
return sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y))-a[i].r-a[j].r;
}
int fa[maxn+5];
int getfa(int x){
return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y){
int fx=getfa(x),fy=getfa(y);
if(fx!=fy) fa[fx]=fy;
}
bool G(int x,int y){
int fx=getfa(x),fy=getfa(y);
return fx==fy;
}
int U,D,L,R;
bool ans[maxm][5];
bool check(int i){
#define ID b[i].id
if(b[i].e==1){
if(G(L,D)) ans[ID][2]=ans[ID][3]=ans[ID][4]=1;else
if(G(U,D)) ans[ID][2]=ans[ID][3]=1;else
if(G(L,R)) ans[ID][3]=ans[ID][4]=1;
else{
if(G(L,U)) ans[ID][4]=1;
if(G(U,R)) ans[ID][3]=1;
if(G(R,D)) ans[ID][2]=1;
}
}else
if(b[i].e==2){
if(G(R,D)) ans[ID][1]=ans[ID][3]=ans[ID][4]=1;else
if(G(U,D)) ans[ID][1]=ans[ID][4]=1;else
if(G(L,R)) ans[ID][3]=ans[ID][4]=1;
else{
if(G(L,U)) ans[ID][4]=1;
if(G(U,R)) ans[ID][3]=1;
if(G(L,D)) ans[ID][1]=1;
}
}else
if(b[i].e==3){
if(G(U,R)) ans[ID][1]=ans[ID][2]=ans[ID][4]=1;else
if(G(U,D)) ans[ID][1]=ans[ID][4]=1;else
if(G(L,R)) ans[ID][1]=ans[ID][2]=1;
else{
if(G(L,U)) ans[ID][4]=1;
if(G(D,R)) ans[ID][2]=1;
if(G(L,D)) ans[ID][1]=1;
}
}else
if(b[i].e==4){
if(G(L,U)) ans[ID][1]=ans[ID][2]=ans[ID][3]=1;else
if(G(U,D)) ans[ID][2]=ans[ID][3]=1;else
if(G(L,R)) ans[ID][1]=ans[ID][2]=1;
else{
if(G(R,U)) ans[ID][3]=1;
if(G(D,R)) ans[ID][2]=1;
if(G(L,D)) ans[ID][1]=1;
}
}
}
const DB eps=1e-4;
void work(){
for(int i=1;i<=n;i++) fa[i]=i;
fa[U]=U,fa[D]=D,fa[L]=L,fa[R]=R;
for(int i=1,l=1,r=n,u=n,d=1,j=1;i<=m;i++){
while(j<=cnt&&e[j].r-b[i].r*2<=-eps) merge(e[j].x,e[j].y),j++;
check(i);
}
}
void init(){
scanf("%d%d%d%d",&n,&m,&w,&h);
for(int i=1,x,y,r;i<=n;i++){
scanf("%d%d%d",&x,&y,&r);
a[i]=a0[i]=a1[i]=(obj){x,y,r,i};
}
std::sort(a0+1,a0+1+n,cmp0);
std::sort(a1+1,a1+1+n,cmp1);
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++) e[++cnt]=(data){i,j,dis(i,j)};
L=n+1,D=n+2,R=n+3,U=n+4;
for(int i=1;i<=n;i++){
e[++cnt]=(data){i,L,a[i].x-a[i].r};
e[++cnt]=(data){i,D,a[i].y-a[i].r};
e[++cnt]=(data){i,R,w-a[i].x-a[i].r};
e[++cnt]=(data){i,U,h-a[i].y-a[i].r};
}
std::sort(e+1,e+1+cnt);
for(int i=1,r,E;i<=m;i++){
scanf("%d%d",&r,&E);
b[i]=(hum){i,E,r};
}
std::sort(b+1,b+1+m);
}
void print(){
for(int i=1;i<=m;i++){
for(int j=1;j<=4;j++) if(!ans[i][j]) printf("%d",j);
putchar(10);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("P4675.in","r",stdin);
freopen("P4675.out","w",stdout);
#endif
init();
work();
print();
return 0;
}