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

1518： ◆adhRKFl5jU：2009/03/01(日) 18:25:56: jid11
-----
/*
flu - solution 2

O(n^2)

JOI spring camp
March 2008

Tetsushi Ito
*/

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

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,c;
int n,m,d,k;

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

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

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

for(i=0;i<n;i++){
for(j=0;j<n;j++){
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;
}

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

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

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）

掲示板管理者へ連絡無料レンタル掲示板