题意：引爆一个炸弹会同时引爆与它相距d的炸弹
重点：由于x，y坐标的范围很大，所以必须离散化，显而易见。在这里可以利用sort+unique进行离散化并存储在myhash中。
其次由于一个点可能多次放炸弹，但只有一次有效，所以用一个vis数组记录
所以对于任意一个炸弹（x，y，d）。首先由x-d，x+d在myhash中确定y在set的范围first_pos，last_pos
然后 再在set中按照y的范围寻找。。。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<queue> 5 #include<set> 6 #include<algorithm> 7 #include<iostream> 8 #include<math.h> 9 using namespace std; 10 const int maxn = 100015; 11 int myhash[ maxn ]; 12 struct node{ 13 int x,y,d; 14 }mine[ maxn ]; 15 struct node2{ 16 int y,id; 17 node2( int a,int b ){ 18 y=a; 19 id=b; 20 } 21 bool operator<( const node2 &tmp ) const 22 { 23 return y<tmp.y; 24 } 25 }; 26 multiset<node2>p[ maxn ]; 27 multiset<node2>::iterator LL,RR,it; 28 queue<int>q; 29 bool vis[ maxn ]; 30 void init( int cnt ){ 31 for( int i=0;i<cnt;i++ ) 32 p[ i ].clear(); 33 memset( vis,false,sizeof( vis )); 34 } 35 int lisanhua( int n ){ 36 sort( myhash,myhash+n ); 37 int cnt; 38 cnt=unique( myhash,myhash+n )-myhash; 39 return cnt; 40 }//return the new number 41 int main(){ 42 int n; 43 int ca=1; 44 while( scanf("%d",&n)!=EOF,n ){ 45 for( int i=0;i<n;i++ ){ 46 scanf("%d%d%d",&mine[i].x,&mine[i].y,&mine[i].d); 47 myhash[ i ]=mine[ i ].x; 48 } 49 int cnt=lisanhua( n ); 50 init( cnt ); 51 for( int i=0;i<n;i++ ){ 52 int pos=lower_bound( myhash,myhash+cnt,mine[i].x )-myhash; 53 p[ pos ].insert( node2( mine[i].y,i )); 54 } 55 printf("Case #%d:\n",ca++); 56 int m; 57 scanf("%d",&m); 58 while( m-- ){ 59 int id; 60 scanf("%d",&id); 61 id--; 62 if( vis[ id ]==true ){ 63 puts("0"); 64 continue; 65 } 66 while( !q.empty() ) 67 q.pop(); 68 int ans=0; 69 q.push( id ); 70 vis[ id ]=true; 71 while( !q.empty() ){ 72 int now_id=q.front(); 73 q.pop(); 74 ans++; 75 int first_pos=lower_bound( myhash,myhash+cnt,mine[ now_id ].x-mine[ now_id ].d )-myhash; 76 int last_pos=upper_bound( myhash,myhash+cnt,mine[ now_id ].x+mine[ now_id ].d )-myhash; 77 //首先由横坐标确定大致的 x 寻找范围 78 for( int pos=first_pos;pos<last_pos;pos++ ){ 79 int dy=mine[ now_id ].d-abs( mine[ now_id ].x-myhash[ pos ] ); 80 LL=p[ pos ].lower_bound( node2( mine[ now_id ].y-dy,0 ) ); 81 RR=p[ pos ].upper_bound( node2( mine[ now_id ].y+dy,0 ) ); 82 //然后再由纵坐标确定 y 的寻找范围 83 for( it=LL;it!=RR;it++ ){ 84 if( vis[ it->id ]==false ){ 85 vis[ it->id ]=true; 86 q.push( it->id ); 87 } 88 } 89 p[ pos ].erase( LL,RR );//必须删除已经爆炸的点！！！ 90 } 91 } 92 printf("%d\n",ans); 93 } 94 } 95 return 0; 96 }
离散化一直是内伤。。。。。