Telecom Company
By Mauricio Amaral, UFU 
Brazil
By Mauricio Amaral, UFU Brazil
Cesario is an analyst at Algar Telecom, and is working on a project to analyze the mobile phone network . He have to develop a system to analyze the scope of each antenna in the network and define the operational costs for sending data to another device, based on the distance between the antennas. The objective of minimizing these costs, finding the best route available. The calculations also aim to find out if it is possible to establish a path between two devices in order to detect serious problems in the network.
Even with all the data available for processing, Cesario has faced problems in implementation due to the high complexity of this algorithm, so you've been hired to help . Its goal is to analyze all the antennas of the Algar Telecom network, noting its coordinates and radii; verify which able to be accessed (within line of sight) antennas, and calculate the shortest path between two specific antennas.
The input consists of several test cases. Since the first line contains a non-negative integer, N (2 ≤ N ≤ 100), which indicates the number of antennas available for the interconnection network. The next N lines, each containing three integers X (0 ≤ X ≤ 1000), Y (0 ≤ Y ≤ 1000) and R (1 ≤ R ≤ 1000), which describe the position of the antenna, X and Y coordinates and its range R (separated by whitespace). The next line contains another non-negative integer, C (1 ≤ C ≤ 100), which describes the amount of calculations to be performed in this network. The following C lines contains 2 integers each, A1 (1 ≤ N ≤ A1) and A2 (1 ≤ N ≤ A2), which describe the
content of the antennas to be used and also separated by whitespace.
The order of the inputs is indicated by number 0.
For each test case, if C you should print lines, each of which represents the distance of the shortest path between the two antennas. Values must be WHOLE, ie, the real part should be truncated (not rounded), and always with a line break. If not identified a route between the antennas should be printed the value -1.
| Sample Input | Sample Output |
|
2 0 3 3 2 1 1 2 1 2 2 1 3 1 1 2 0 0 1 1 2 2 4 1 3 2 3 3 1 3 3 0 |
2 -1 1 -1 1 0 |