2015
05-24

# Mines

Terrorists put some mines in a crowded square recently. The police evacuate all people in time before any mine explodes. Now the police want all the mines be ignited. The police will take many operations to do the job. In each operation, the police will ignite one mine. Every mine has its "power distance". When a mine explodes, any other mine within the power distance of the exploding mine will also explode. Please NOTE that the distance is Manhattan distance here.

More specifically, we put the mines in the Cartesian coordinate system. Each mine has position (x,y) and power distance d.

The police want you to write a program and calculate the result of each operation.

There are several test cases.
In each test case:
Line 1: an integer N, indicating that there are N mines. All mines are numbered from 1 to N.
Line 2…N+1: There are 3 integers in Line i+1 (i starts from 1). They are the i-th mine’s position (xi,yi) and its power distance di. There can be more than one mine in the same point.
Line N+2: an integer M, representing the number of operations.
Line N+3…N+M+2 : Each line represents an operation by an integer k meaning that in this operation, the k-th mine will be ignited. It is possible to ignite a mine which has already exploded, but it will have no effect.

1<=M<=N<=100000，0<=xi,yi<=10^9，0<=di<=10^9

Input ends with N=0.

There are several test cases.
In each test case:
Line 1: an integer N, indicating that there are N mines. All mines are numbered from 1 to N.
Line 2…N+1: There are 3 integers in Line i+1 (i starts from 1). They are the i-th mine’s position (xi,yi) and its power distance di. There can be more than one mine in the same point.
Line N+2: an integer M, representing the number of operations.
Line N+3…N+M+2 : Each line represents an operation by an integer k meaning that in this operation, the k-th mine will be ignited. It is possible to ignite a mine which has already exploded, but it will have no effect.

1<=M<=N<=100000，0<=xi,yi<=10^9，0<=di<=10^9

Input ends with N=0.

3
0 0 0
1 1 2
2 2 2
3
1
2
3
0

Case #1:
1
2
0

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
const int maxn = 110005;
const int inf = 2000000005;
struct NODE{
int y, dis;
NODE(){
}
NODE(int _y, int _dis){
y = _y; dis = _dis;
}
bool operator <(const NODE &tmp)const{
if(y == tmp.y) return dis < tmp.dis;
return y < tmp.y;
}
};
struct POINT{
int x, y, dis;
POINT() {
}
POINT(int _x, int _y, int _dis){
x = _x;
y = _y;
dis = _dis;
}
}df[maxn], myque[1111111];
int n, m, hash[maxn], num;
vector<NODE>mygraph[maxn];
void init(){
num = 0;
for(int i = 0; i < maxn; i++) mygraph[i].clear();
}
for(int i = 1; i <= n ; i++){
scanf("%d%d%d", &df[i].x, &df[i].y, &df[i].dis);
hash[num++] = df[i].x;
}
sort(hash, hash + num);
num = unique(hash, hash + num) - hash;
for(int i = 1; i <= n; i++){
int id = lower_bound(hash, hash + num, df[i].x) - hash;
mygraph[id].push_back(NODE(df[i].y, df[i].dis));
}
}
int fuckit(int fuckid){
int head = 0, tail = 0, ret = 0;
vector<NODE>::iterator vectoriterator1, vectoriterator2, tmpvectoriterator;
myque[tail++] = POINT(df[fuckid].x, df[fuckid].y, df[fuckid].dis);
int pos1 = lower_bound(hash, hash + num, now.x - now.dis) - hash;
int pos2 = upper_bound(hash, hash + num, now.x + now.dis) - hash;
for(; pos1 != pos2; pos1++){
int fucknum = hash[pos1];
int fucky = now.dis - abs(fucknum - now.x);
int id = lower_bound(hash, hash + num, fucknum) - hash;
vectoriterator1 = lower_bound(mygraph[id].begin(), mygraph[id].end(), NODE(now.y - fucky, -1));
vectoriterator2 = upper_bound(mygraph[id].begin(), mygraph[id].end(), NODE(now.y + fucky, inf));
tmpvectoriterator = vectoriterator1;
for(; vectoriterator1 != vectoriterator2; vectoriterator1++){
NODE tmp  = *vectoriterator1;
myque[tail++] = POINT(fucknum, tmp.y, tmp.dis);
ret++;
}
mygraph[id].erase(tmpvectoriterator, vectoriterator2);
}
}
return ret;
}
int main(){
int testcases = 0;
while(scanf("%d", &n) != EOF && n){
init();
printf("Case #%d:\n", ++testcases);
for(int i = 0; i < num; i++) {
sort(mygraph[i].begin(), mygraph[i].end());
}
scanf("%d", &m);
for(int i = 1; i <= m; i++){
int k;
scanf("%d", &k);
int sum = fuckit(k);;
printf("%d\n", sum);
}
}
return 0;
}


1. 哪个巫甄又坏又蠢，还说什么喜欢秦漠，不知道这场比赛对秦神很重要吗！还仗着自己是警察就仗势欺人，异想天开地说自己最配秦神。我大黑桃一出场，分分钟秒了她，让她看看谁才是秦家的少夫人！哈哈哈