したらばTOP ■掲示板に戻る■ 全部 1-100 最新50 | メール | |

管理人の独り言（プログラミング関連）

1519： ◆adhRKFl5jU：2009/03/01(日) 18:26:30
jid12
-----
/*
flu - solution 3

O(n)

JOI spring camp
March 2008

Tetsushi Ito
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int table[1000][1000][10];

int x[100000], y[100000];
int num[100000];
int list[100000][10];

int dist[100000];

int queue[100000];
int pos,queue_end;

int main(void)
{
int i,j,f,a,b,c,s,t,u;
int n,m,d,k;

scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&d);
scanf("%d",&k);

for(i=0;i<(1000/d)+1;i++)
for(j=0;j<(1000/d)+1;j++)
table[i][j][0]=0;

for(i=0;i<n;i++){
scanf("%d %d",&x[i],&y[i]);
a = x[i]/d;
b = y[i]/d;
table[a][b][table[a][b][0]+1]=i;
table[a][b][0]++;
}

for(i=0;i<n;i++) num[i]=0;

for(i=0;i<n;i++){
a=x[i]/d;
b=y[i]/d;
for(s=a-1;s<=a+1;s++){
if(s<0) continue;
for(t=b-1;t<=b+1;t++){
if(t<0) continue;
for(u=0;u<table[s][t][0];u++){
j=table[s][t][u+1];
if(i==j) continue;
if((x[i]-x[j])*(x[i]-x[j])
+ (y[i]-y[j])*(y[i]-y[j])
<= d*d){
list[i][num[i]]=j;
num[i]++;
}
}
}
}
}

/*
for(j=0;j<n;j++){
printf("%d:",j);
for(i=0;i<num[j];i++)
printf("%d ",list[j][i]);
printf("\n");
}
exit(1);
*/

for(i=0;i<n;i++) dist[i]=-1;
dist[0]=0;

pos=0;
queue[0]=0;
queue_end=1;
while(-1){
i=queue[pos];
pos++;
for(j=0;j<num[i];j++){
if(dist[list[i][j]]!=-1) continue;
queue[queue_end]=list[i][j];
queue_end++;
dist[list[i][j]]=dist[i]+1;
// printf("%d ",list[i][j]);
}
if(pos==queue_end) break;
}

c=0;
for(i=0;i<n;i++){
// printf("%d ",dist[i]);
if(k-m+1 <= dist[i] && dist[i] <= k) c++;
}
printf("%d\n",c);

return 0;
}
新着レスの表示

名前： E-mail（省略可）：

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）
掲示板管理者へ連絡 無料レンタル掲示板