CS
Problems Base course RU

Problem

A tour along the Hilbert curve

sorting points geodata heuristic bit tricks

A courier must visit n points on a square map of 65,536 × 65,536. Finding the shortest route is the travelling salesman problem, and for large n it cannot be solved exactly. But there is a quick way to get a decent route: number the map’s cells along a Hilbert curve and visit the points in increasing order of their cell numbers.

A Hilbert curve of order 16 visits every cell of the map once. The number of cell (x, y) is computed as follows: start with d = 0 and for s = 215, 214, …, 1 in turn take a step:

  • rx = 1 if bit s of x is set, otherwise 0; likewise ry for y;
  • d increases by s² · ((3·rx) XOR ry);
  • if ry = 0: when rx = 1, replace x with s − 1 − x and y with s − 1 − y; then swap x and y.

Order the points by cell number (points with the same number in input order) and print the length of the polyline that passes through them in this order. Distances are ordinary straight-line ones; there is no need to return to the start.

Input

The first line holds n (1 ≤ n ≤ 2·10⁵). Then n lines with coordinates x and y (0 ≤ x, y < 65,536).

Output

The length of the route. The answer is accepted with a relative error of 10⁻⁶.

Examples

Example 1

Input
6
0 0
65535 0
0 65535
65535 65535
32768 32768
100 30000
Output
223750.086

Limits

Time · Python
9000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
6 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

A cell’s number depends only on its coordinates. Compute it for each point, sort, and add up the segment lengths.

2The idea

The sort key is the pair (the cell’s number on the curve, the point’s number in the input). The number is computed in 16 steps, one per bit, as in the statement. The sort is O(n log n), the route length one pass with math.hypot.

3Walkthrough

Why such a route is good: neighbouring numbers on the Hilbert curve are neighbouring cells of the map, and points that end up next to each other in the visiting order are almost always next to each other on the map too. The curve enters each quarter of the map once and covers it completely before leaving, and the same inside each quarter of a quarter. Building a route this way was proposed by John Bartholdi and Loren Platzman in the 1980s; they used the Sierpiński curve, but such curves have similar properties: on random points the route comes out about a quarter longer than the shortest, and in the worst case the ratio grows only as the logarithm of the number of points.

The fourth test is all 19,073 M5+ earthquakes of 2015–2025 on a world grid. The route along the Hilbert curve is about 2.77 million cells. Visiting them in Z-order, as geohash sorts, comes out 1.3 times longer: the Z-curve jumps between quarters. In catalogue order, that is, by time, 171 times longer, and in random order 209 times.

More about the curves and where databases use them in the article “Hilbert curves and geohash”.

3+Solution
4Complexity

O(n log n): 16 steps per number and a sort.

5Common mistakes
  • Z-order instead of Hilbert. Interleaving the bits of x and y is simpler, but it is a different curve and a different route, already on the example.
  • Forgetting the rotation. Without the replacement and swap of coordinates in a step, the number is not a Hilbert one: the curve breaks at quarter boundaries.
  • An unstable sort. Points in the same cell must be taken in input order: the third test.

Algorithms behind it

GEO Technique Hilbert curves and geohash Number the plane so that neighbours on the map stand together in a one-dimensional index: Z-order, geohash, Hilbert. O(k) per number 1 problem GRA Algorithm Travelling salesman problem The shortest tour of all points: nearest neighbour, 2-opt with neighbour lists, Or-opt, the Held–Karp bound. NP-hard; exactly O(2ⁿ · n²) 2 problems
The algorithms catalogue