Drone range
A delivery service carries medicines to villages by drone. A drone flies in a straight line from village to village and recharges in every village where it lands, so its range limits only the length of one hop, not the whole route. The dispatcher receives questions “what range is needed to fly from village a to village b?”; for each question find the smallest such range. Landing is allowed in any villages from the list, any number of times.
Two tests are the real 675 towns and villages of the South Moravian Region from the GeoNames gazetteer on a plane, in metres; village number 1 is Brno. One of them has two hundred thousand questions.
Input
The first line holds n and q (1 ≤ n ≤ 1000, 1 ≤ q ≤ 200,000), the number of villages and questions. Then n lines with the coordinates of the villages x and y, integers with |x|, |y| ≤ 10⁶; villages may coincide. Then q lines with village numbers a and b (1 ≤ a, b ≤ n).
Output
For each question, the smallest range in the same units, with three digits after the point (the answer is accepted with a relative error of 10⁻⁶). If a = b, there is nowhere to fly, and the answer is 0.
Examples
Example 1
6 5 0 0 4 3 8 0 30 0 34 4 16 20 1 3 1 4 6 2 5 4 3 3
5.000 22.000 20.809 5.657 0.000
Example 2
4 4 0 0 5 0 6 0 20 0 1 4 4 1 2 3 2 2
14.000 14.000 1.000 0.000
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
For one question the range can be found by binary search, checking by a traversal of the graph whose edges are pairs of villages within it. But there are two hundred thousand questions. Which structure answers all the “how much is needed to connect” questions at once?
2Hint 2
The article on the minimum spanning tree proves that the path along the spanning tree between two vertices makes the longest edge on the path as small as possible. It remains to find quickly the longest edge on a path in a tree.
3The idea
The answer to a question (a, b) is the longest wire on the path between a and b in the minimum spanning tree. Less is impossible: if this wire is thrown out of the tree, a and b end up in different parts, and any route of the drone hops between the parts at least once, and the shortest such hop is exactly the wire thrown out. More is not needed: the path along the tree is a route. The tree is built once, and after that each question is about a path in the tree.
4Walkthrough
The graph is complete, so the spanning tree is conveniently built by Prim without a heap in O(n²), on squared distances, which are integers and compare exactly. Then for each village from which at least one question is asked, traverse the tree from that village and record for all the others the longest edge on the path: for a neighbour it is the maximum of the value at the current vertex and the length of the edge between them. A traversal is O(n), there are at most n traversals, O(n²), and after that each question is one table lookup. The square root is taken when printing.
There are other ways too. Questions can be grouped by village so as to do without a table of a million numbers. Binary lifting on the tree answers in O(log n) per question; that is what is done when there are a million villages and the table does not fit in memory. Or the tree need not be built separately at all: go through the wires with Kruskal, and at the moment a and b first end up in one piece, record the length of the wire, which is the answer; the questions are then kept in the pieces of a disjoint-set union and moved from the smaller piece to the larger on merging.
On Moravia the answer to any question about Brno is 5644.887 m: Brno has no closer neighbour in the gazetteer, so any route from Brno begins with a hop at least that long.
4+Solution
5Complexity
O(n²) for the spanning tree and traversals and O(1) per question: O(n² + q) in all. A traversal of the tree for every question is O(n·q), more than a hundred million steps in the fourth test.
6Common mistakes
- The shortest path instead of the spanning tree. The shortest route by sum of lengths is the direct hop, and its length is almost always greater than the answer. In the first example from village 1 to village 3 it is 8 in a straight line, while with a landing in the second village a range of 5 is enough.
- A traversal for every question. The idea is right, but two hundred thousand traversals of a tree of 675 vertices will not make it in time.
- The longest wire of the whole spanning tree. It is needed only if the path goes through it; in the second example from village 2 to village 3 a range of one is enough.