无限RE求助
查看原帖
无限RE求助
116251
破忆楼主2021/11/7 18:03

本地、本校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;
}
2021/11/7 18:03
加载中...