Closest Points

All submissions for this problem are available.
Crisis at Byte Town!
There have been 100000 (of course, in base 2) instances of bank robberies in the past month! That is, more than one robbery in a day in average and the Byte Town Police Department (BTPD) is dumb founded. Chef, the honorable President of Byte Town, has pledged to solve the problem for good.
Chef investigated and found out that Byte Town has a large number of BTPD response centers and an equally large (if not larger) number of banks. Each bank has an alert mechanism that alerts a BTPD response center assigned to the bank. That response center is then responsible for sending in a strike team. The response center assigned to some bank is called the respondent for this bank. Unfortunately, that is the problem. The current assignment of which BTPD response center responds to an alert by a bank is outdated. Chef has decided to upgrade this system, in lieu of which, you have to solve this problem.
Byte Town, being the quintessential challenge for every programmer, is Euclidean 3D space. Each response center and each bank is represented by some point in this 3D space. There are N response centers and Q banks in Byte Town. BTPD response centers are labeled by integers 0, 1, ..., N1 and i^{th} response center is represented by the point with coordinates (X_{i}, Y_{i}, Z_{i}). Banks are labeled by integers 0, 1, ..., Q1 and j^{th} bank is represented by the point with coordinates (A_{j}, B_{j}, C_{j}). No two buildings (banks, as well as response centers) will ever be at the same point. Your task is to assign for each bank the BTPD response center that will be the respondent for this bank. A response center can be the respondent for more than one bank. But every bank should have exactly one respondent.
Bluntly speaking, your goal is to minimize the Euclidian distance between bank and its respondent. The Euclidian distance between i^{th} response center and j^{th} bank is equal to the square root of the number
(X_{i} – A_{j})^{2} + (Y_{i} – B_{j})^{2} + (Z_{i} – C_{j})^{2}.
Denote by C[j] the closest response center to the j^{th} bank and by D[j] the distance to it. Your absolute goal is to find C[j] for all banks. But since it is the challenge problem you can get accepted even if your assignment will be not optimal. But to get accepted you need to find C[j] for at least one value of j. To make things clear we note that C[j] could be not unique, so by the phrase "to find C[j]" we mean to find any response center that has distance D[j] to the j^{th} bank.
Input
The first line of the input file contains an integer N, the number of BTPD response centers. Each of the following N lines contains three integers X_{i}, Y_{i}, Z_{i}, the coordinates of the i^{th} response center. The next line contains an integer Q, the number of banks. Each of the following Q lines contains three integers A_{j}, B_{j}, C_{j}, the coordinates of the j^{th} bank. Each pair of consecutive numbers in every line is separated by exactly one space.
Output
For each of the Q banks from the input file you should print exactly one line that contains the number from the set {0, 1, ..., N1}, the response center that you have assigned to the corresponding bank. So the (j+1)^{th} line of the output file should contain the respondent of the j^{th} bank. Just to reiterate, your output will be considered as correct if and only if you print exactly Q integers I_{0}, I_{1}, ..., I_{Q1}, each from 0 to N1 (inclusive) such that for at least one value of j from 0 to Q1 (inclusive) we have that the I_{j}^{th} response center is the closest response center to the j^{th} bank.
Scoring
Your score for a test file is the total number of banks for which you find the closest possible response center. Formally the score is the number of those values of j from 0 to Q1 such that the distance between j^{th} bank and the response center that you have assigned to it is equal to D[j]. The total score for a submission is the average score across all the test files.
Constraints
1 ≤ N, Q ≤ 50000
Each point in the input file has coordinates with absolute value no more than 10^{9}.
That is, X_{i}, Y_{i}, Z_{i}, A_{j}, B_{j}, C_{j} ≤ 10^{9}
Example
Input: 3 1 0 0 0 0 1 0 1 0 2 0 1 0 0 0 1 Output: 0 1
Explanation
Consider the 0^{th} bank. It has coordinates (0, 1, 0). Hence the squares of distances from this bank to response centers are
 to the 0^{th} center: (1 – 0)^{2} + (0 – (1))^{2} + (0 – 0)^{2} = 1 + 1 + 0 = 2;
 to the 1^{st} center: (0 – 0)^{2} + (0 – (1))^{2} + (1 – 0)^{2} = 0 + 1 + 1 = 2;
 to the 2^{nd} center: (0 – 0)^{2} + (1 – (1))^{2} + (0 – 0)^{2} = 0 + 2^{2} + 0 = 4.
Thus, the closest response centers to the 0^{th} bank are both 0^{th} and 1^{st} response centers. Since in the output we assign 0^{th} response center to this bank we find one of the closest response centers to this bank and it will be counted in our resulting score.
Now consider the 1^{st} bank. It has coordinates (0, 0, 1). Hence the squares of distances from this bank to response centers are
 to the 0^{th} center: (1 – 0)^{2} + (0 – 0)^{2} + (0 – (1))^{2} = 1 + 0 + 1 = 2;
 to the 1^{st} center: (0 – 0)^{2} + (0 – 0)^{2} + (1 – (1))^{2} = 0 + 0 + 2^{2} = 4;
 to the 2^{nd} center: (0 – 0)^{2} + (1 – 0)^{2} + (0 – (1))^{2} = 0 + 1 + 1 = 2.
Thus, the closest response centers to the 1^{st} bank are both 0^{th} and 2^{nd} response centers. Since in the output we assign 1^{st} response center to this bank we fail to find the closest response center to this bank and it will not be counted in our resulting score.
Thus, total score for this test case would be 1. Since we find the closest response center to at least one bank such output will be considered as correct.
Test Generation
In each official test file N = Q = 50000. Coordinates of banks and response centers are generated using different strategies. In some tests coordinates are uniformly distributed within its range while other tests created specifically to fail certain heuristics.
Author:  gamabunta 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/CLOSEST 
Tags  challenge, gamabunta, geometry, june12, kdtree 
Date Added:  24042011 
Time Limit:  0.499541 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 