http://acm.hdu.edu.cn/showproblem.php?pid=4400
题意：
在笛卡尔坐标中有多个炸弹，每个炸弹有一个坐标值和一个爆炸范围。现在有多次操作，每次引爆一个炸弹，问每次操作会有多少个炸弹爆炸。
思路：
需要注意的是一个炸弹爆炸后会引起别的炸弹爆炸，然后别的炸弹爆炸后又会引起别的炸弹爆炸。
可以考虑bfs，但是必须需要优化，首先对x坐标进行离散化，然后将该坐标的y值和id值（第几个炸弹）存入multiset中，不同的x存入不同的multiset中。当我们进行寻找时，首先可以确定x的范围，当确定了x的范围之后，对于该x值我们又可以确定y的范围，这样只需要在multiset中进行二分查找即可。不得不说这个做法实在是太妙了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = +; int n, num;
int x[maxn],y[maxn],d[maxn],b[maxn];
bool del[maxn]; struct node
{
int y,id;
node(int y, int id):y(y),id(id){}
bool operator< (const node& rhs) const
{
return y<rhs.y;
}
}; multiset<node> s[maxn];
multiset<node>::iterator ly, ry, it; void solve()
{
priority_queue<int> q;
memset(del,false,sizeof(del));
int m; scanf("%d",&m);
while(m--)
{
int t; scanf("%d",&t); t--;
if(del[t]) {puts("");continue;}
while(!q.empty()) q.pop();
q.push(t);
del[t] = true;
int ans = ;
while(!q.empty())
{
ans++;
t = q.top(); q.pop();
int lx = lower_bound(b,b+num,x[t]-d[t])-b;
int rx = upper_bound(b,b+num,x[t]+d[t])-b;
for(int i=lx;i<rx;i++)
{
int dis = d[t]-abs(x[t]-b[i]);
ly = s[i].lower_bound(node(y[t]-dis,));
ry = s[i].upper_bound(node(y[t]+dis,));
for(it=ly;it!=ry;it++)
{
if(!del[it->id])
{
del[it->id] = true;
q.push(it->id);
}
}
s[i].erase(ly,ry);
}
}
printf("%d\n",ans);
}
} int main()
{
//freopen("in.txt","r",stdin);
int kase = ;
while(~scanf("%d",&n) && n!=)
{
printf("Case #%d:\n",++kase);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&d[i]);
b[i] = x[i];
}
sort(b,b+n);
num = unique(b,b+n)-b;
for(int i=;i<n;i++) s[i].clear();
for(int i=;i<n;i++)
{
int tmp = lower_bound(b,b+num,x[i])-b;
s[tmp].insert(node(y[i],i));
}
solve();
}
return ;
}