제출 #1105

#제출 시각아이디문제언어결과실행 시간메모리
1105hana5505개구리 (KOI13_frog)C++98
16.94 / 22
1000 ms2448 KiB
#include<stdio.h>
struct pp{
	int x,y;
}ar[100001];
int n,r,d,que[100001],aa[100001];
int ok(int i,int j)
{
	int tmp;

	if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r){
		if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r+d) return 1;
		if(ar[i].y-r-d<=ar[j].y && ar[j].y<=ar[i].y) return 1;
	}
	if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r){
		if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r+d) return 1;
		if(ar[i].x-r-d<=ar[j].x && ar[j].x<=ar[i].x) return 1;
	}
	tmp=i;
	i=j;
	j=tmp;
	if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r){
		if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r+d) return 1;
		if(ar[i].y-r-d<=ar[j].y && ar[j].y<=ar[i].y) return 1;
	}
	if(ar[i].y<=ar[j].y && ar[j].y<=ar[i].y+r){
		if(ar[i].x<=ar[j].x && ar[j].x<=ar[i].x+r+d) return 1;
		if(ar[i].x-r-d<=ar[j].x && ar[j].x<=ar[i].x) return 1;
	}
	return 0;
}
int main()
{
	int i,st,head,tail,t,mx=0;

	scanf("%d %d",&n,&r);
	for(i=1;i<=n;i++){
		scanf("%d %d",&ar[i].x,&ar[i].y);
		if(ar[i].x==0 && ar[i].y==0) st=i;
	}
	scanf("%d",&d);

	que[1]=st;
	head=tail=1;
	aa[st]=1;
	while(head<=tail){
		t=que[head++];
		for(i=1;i<=n;i++){
			if(!aa[i] && ok(t,i)){
				aa[i]=1;
				que[++tail]=i;
			}
		}
	}

	for(i=1;i<=n;i++){
		if(aa[i] && ar[i].x+ar[i].y>mx) mx=ar[i].x+ar[i].y;
	}

	printf("%d",mx+2*r);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...