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

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

1522： ◆adhRKFl5jU：2009/03/01(日) 18:28:48
jid15
問題番号 7
点数 100
-----
/*
TASK: Flu
LANG: C++
NAME: Kazuhiro Hosaka JPN13
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i=a; i!=b; ++i) cout << *i << " "; cout << endl; }
template<class T> void pvp(T a, T b) { for (T i=a; i!=b; ++i) cout << "(" << i->first << ", " << i->second << ") "; cout << endl; }

int dx[2610],dy[2610],len;

int N,M,D,K;
int X[100010],Y[100010];
int table[1030][1030];
int infect[100010];
int que[100010],*qb,*qe;

int main() {
//freopen("flu.in", "r", stdin);

int u,v;
int h,x,y;
int ans;

scanf("%i%i%i%i", &N, &M, &D, &K);

memset(table, ~0, sizeof(table));
for (u=0; u<N; ++u) {
scanf("%i%i", &X[u], &Y[u]);
table[X[u] += 10][Y[u] += 10] = u;
}

for (x=-D; x<=D; ++x) for (y=-D; y<=D; ++y) if (x|y) {
if (x * x + y * y <= D * D) dx[len] = x, dy[len] = y, ++len;
}

qb = qe = que;
memset(infect, ~0, sizeof(infect));
infect[*qe++ = 0] = 0;
while (qb != qe) {
if (infect[u = *qb++] > K) break;
for (h=0; h<len; ++h) {
v = table[X[u] + dx[h]][Y[u] + dy[h]];
if (~v && !~infect[v]) {
infect[*qe++ = v] = infect[u] + 1;
}
}
}

ans = 0;
for (u=0; u<N; ++u) if (~infect[u]) {
if (K - M < infect[u] && infect[u] <= K) {
++ans;
}
}

printf("%i\n", ans);


return 0;
}
新着レスの表示

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

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

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

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