（1） KD树，但实际没有STL快，3000+
/* 4400 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct Point_t {
int x, y, d, id; Point_t() {}
Point_t(int x, int y, int d, int id):
x(x), y(y), d(d), id(id) {} } Point_t; typedef struct node_t{
int axis;
int id;
int l, r;
} node_t; const int maxn = 1e5+;
Point_t P[maxn];
node_t nd[maxn];
bool visit[maxn];
int Q[maxn];
int L, head, tail; bool compx(const Point_t& a, const Point_t& b) {
return a.x < b.x;
} bool compy(const Point_t& a, const Point_t& b) {
return a.y < b.y;
} bool compid(const Point_t& a, const Point_t& b) {
return a.id < b.id;
} int newNode() {
++L;
nd[L].l = nd[L].r = ; return L;
} int create(int l, int r, int d) {
if (l > r) return ; int rt = newNode();
nd[rt].axis = d & ;
if (l == r) {
nd[rt].id = P[l].id;
return rt;
} if (d & ) {
sort(P+l, P+r+, compy);
} else {
sort(P+l, P+r+, compx);
} int mid = (l + r) >> ; nd[rt].id = P[mid].id;
nd[rt].l = create(l, mid-, d+);
nd[rt].r = create(mid+, r, d+); return rt;
} int Distance(int i, int j) {
return abs(P[i].x-P[j].x) + abs(P[i].y-P[j].y);
} void search(int rt, int kth) {
if (rt == )
return ; int i, j, k;
int id = nd[rt].id;
int dis = Distance(id, kth); if (dis <= P[kth].d) {
if (!visit[id]) {
visit[id] = true;
Q[tail++] = id;
}
} if (nd[rt].axis) {
// y
if (dis <= P[kth].d) {
search(nd[rt].l, kth);
search(nd[rt].r, kth);
} else {
int dy = abs(P[id].y - P[kth].y);
if (dy > P[kth].d) {
if (P[id].y <= P[kth].y)
search(nd[rt].r, kth);
else
search(nd[rt].l, kth);
} else {
search(nd[rt].l, kth);
search(nd[rt].r, kth);
}
} } else { // x
if (dis <= P[kth].d) {
search(nd[rt].l, kth);
search(nd[rt].r, kth);
} else {
int dx = abs(P[id].x - P[kth].x);
if (dx > P[kth].d) {
if (P[id].x <= P[kth].x)
search(nd[rt].r, kth);
else
search(nd[rt].l, kth);
} else {
search(nd[rt].l, kth);
search(nd[rt].r, kth);
}
}
}
} void init() {
L = ;
memset(visit, false, sizeof(visit));
} int solve(int rt, int k) {
if (visit[k])
return ; head = tail = ;
visit[k] = true;
Q[tail++] = k; while (head < tail) {
search(rt, Q[head++]);
} return tail;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t = ;
int n, q;
int kth, ans; while (scanf("%d", &n)!=EOF && n) {
rep(i, , n) {
scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].d);
P[i].id = i;
}
init();
int rt = create(, n-, );
sort(P, P+n, compid);
scanf("%d", &q);
printf("Case #%d:\n", ++t);
while (q--) {
scanf("%d", &kth);
ans = solve(rt, kth-);
printf("%d\n", ans);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
（2） STL 1400+
/* 4400 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct node_t {
int x, y, d; node_t() {}
node_t(int x, int y, int d):
x(x), y(y), d(d) {} friend bool operator< (const node_t& a, const node_t& b) {
return a.y < b.y;
} } node_t; typedef struct {
int y, id;
} pair_t; const int maxn = 1e5+;
int X[maxn];
bool visit[maxn];
node_t nd[maxn];
vector< pii > vc[maxn];
int n, m; bool comp(const node_t& a, const node_t& b) {
return a.y < b.y;
} void init() {
memset(visit, false, sizeof(visit)); rep(i, , n) {
X[i] = nd[i].x;
vc[i].clr();
} sort(X, X+n);
m = unique(X, X+n) - X;
node_t tmp; rep(i, , n) {
int id = lower_bound(X, X+m, nd[i].x) - X;
vc[id].pb(mp(nd[i].y, i));
} rep(i, , m)
sort(all(vc[i]));
} int bfs(int kth) {
if (visit[kth])
return ; int ret = ;
int x, y, dx, dy;
int lx, rx, ly, ry;
int id, xid;
vector< pii >::iterator iter, liter, riter;
queue<int> Q;
pii p; visit[kth] = true;
Q.push(kth);
p.sec = -; while (!Q.empty()) {
kth = Q.front();
Q.pop();
id = lower_bound(X, X+m, nd[kth].x) - X;
lx = lower_bound(X, X+m, nd[kth].x - nd[kth].d) - X;
rx = upper_bound(X, X+m, nd[kth].x + nd[kth].d) - X;;
for (xid=lx; xid<rx; ++xid) {
x = X[xid];
dx = abs(x - nd[kth].x);
dy = nd[kth].d - dx;
ly = nd[kth].y - dy;
ry = nd[kth].y + dy; // find lower_bound
p.fir = ly;
p.sec = -;
liter = lower_bound(all(vc[xid]), p); // find upper_bound
p.fir = ry;
p.sec = maxn;
riter = upper_bound(all(vc[xid]), p); for (iter=liter; iter!=riter; ++iter) {
int k = iter->sec;
if (!visit[k]) {
visit[k] = true;
++ret;
Q.push(k);
}
} // vc[xid].erase(liter, riter);
}
} return ret;
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int q;
int t = ;
int ans; while (scanf("%d", &n)!=EOF && n) {
rep(i, , n)
scanf("%d %d %d", &nd[i].x, &nd[i].y, &nd[i].d);
init();
scanf("%d", &q);
printf("Case #%d:\n", ++t);
int kth;
while (q--) {
scanf("%d", &kth);
--kth;
ans = bfs(kth);
printf("%d\n", ans);
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}