Problems Base course RU

A map at every zoom

points geodata maps and navigation compression precomputation binary search

A map of hiking trails shows them at different zoom levels. At each level the trails are simplified by the Ramer–Douglas–Peucker algorithm with its own tolerance ε: the smaller the scale, the larger the tolerance. A designer is choosing the zoom scale and wants to know, for each candidate ε, how many points of all the trails will remain on the map. There are tens of thousands of candidates and thousands of trails.

The simplification rules are the same as in the problem “Simplify a trail”: the ends of each trail remain; for a pair of kept points the point farthest from the segment between them is found (among equidistant ones, the one with the smaller number); it remains and splits the pair in two if its distance is strictly greater than ε, otherwise all the points between the ends of the pair are thrown out. Each trail is simplified separately.

The second test is the mountain paths and tracks south of Almaty from OpenStreetMap, in whole metres from the centre of the map.

Input

The first line holds the number of trails T (T ≥ 1). Each trail is a number of points n (n ≥ 2) and n lines with coordinates x y in order. There are at most 100,000 points in all the trails; all coordinates are integers, |x|, |y| ≤ 16,000; points may repeat. Then the number of queries q (1 ≤ q ≤ 100,000) and a line of q integer tolerances ε (0 ≤ ε ≤ 10⁵).

Output

For each tolerance, on a separate line, how many points of all the trails remain after simplification with that tolerance.

Examples

Example 1

Input

2
13
0 0
6 1
12 1
13 3
7 4
1 5
2 7
8 8
14 8
15 10
17 15
20 16
24 21
7
0 0
4 1
8 0
14 1
30 2
20 1
10 0
13
0 1 2 3 4 5 6 7 8 9 10 11 12

Output

Limits

Time · Python: 6000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 5 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

Rerunning the simplification for each tolerance is a hundred thousand passes over a hundred thousand points. What in the algorithm’s work does not depend on ε?

2Hint 2

The point farthest from a segment does not depend on the tolerance. So for any ε the algorithm splits a trail along the same tree, and ε decides only where the splitting stops. When does a point survive at tolerance ε?

3The idea

Run the algorithm once, splitting everything that can be split, and record for each point its threshold: the largest integer tolerance at which it remains. A point remains at ε if its distance exceeds ε and so does that of every ancestor in the split tree: once an ancestor drops out, its pair is not split, and the point is never reached. So the threshold is the minimum along the chain of ancestors. After that, the answer to a query is how many thresholds are at least ε, plus the ends of the trails: a sort and binary search.

4Walkthrough

Compare distances in integers, as in the problem “Simplify a trail”: for a pair with L = |P_j − P_i|², compute v = d²·L for each point between them (if L = 0, simply d²). The farthest point is the first maximum of v. Its own integer threshold is the largest e with d > e, that is, with e²·L < v: this is e = ⌊√((v − 1) / L)⌋, an integer square root. The point’s threshold is min(e, the parent’s threshold); push both halves onto the stack together with this number. Points with v = 0 lie on the segment and survive no ε ≥ 0; their pairs are not split further.

Put all the thresholds into one array and sort it. The answer for ε is 2·T + (the number of thresholds ≥ ε), given by binary search.

The numbers: with coordinates up to 16,000 the squared distance is up to 2·32,000² ≈ 2·10⁹, and v up to 4.2·10¹⁸. That still fits in int64.

4+Solution

5Complexity

One simplification pass is O(N log N) on typical trails and O(N²) in the worst case, sorting the thresholds O(N log N), each query O(log N).

6Common mistakes

A threshold equal to the point’s own distance. It seems that descendants in the tree are closer to their segments than ancestors, but that is not so. In the switchback example point 6 is 11.70 from its segment, while its parent, point 3, is 7.15; at a tolerance of 8 the parent drops out, and point 6 with it. This is a wrong solution; on the real trails of the second test it errs on most queries.
Simplifying anew for each query. Correct, but a hundred thousand passes over a hundred thousand points will not fit in any time limit.
Thresholds in floating point. You can compare ε with a real-valued distance, but at points where the distance is exactly an integer (it happens with integer coordinates) an error in the last digit flips the answer.

Algorithms behind it

GEO Algorithm Ramer–Douglas–Peucker line simplification Simplify a polyline without losing its shape: the point farthest from the chord stays if it is farther than the tolerance. O(n log n) typically, O(n²) in the worst case 2 problems SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems