Routes with no step back
A courier does not like to wander. They walk from crossing s to crossing t by one rule: each next crossing must be closer to t in a straight line than the one they are standing on now. How many different routes do they have?
The city has n crossings with integer coordinates in metres and m pieces of street, each of which can be walked in both directions. A route is a sequence of pieces of street, so two different pieces between the same crossings give different routes. There are also loop pieces that return to the same crossing. If s = t, there is one route: going nowhere. There can be very many routes; print their number modulo 109 + 7.
One of the tests is the real streets of Almaty from OpenStreetMap, from the Almaty-2 railway station to MEGA Alma-Ata.
Input
The first line holds n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 2·105). Then n lines with the coordinates of the crossings x y (|x|, |y| ≤ 109), then m lines a b, a piece of street between crossings a and b (1 ≤ a, b ≤ n). The last line holds s and t.
Output
The number of routes from s to t modulo 109 + 7.
Examples
Example 1
9 12 0 0 100 0 200 0 0 100 100 100 200 100 0 200 100 200 200 200 1 2 2 3 4 5 5 6 7 8 8 9 1 4 2 5 3 6 4 7 5 8 6 9 9 1
6
Example 2
5 4 0 0 300 0 300 200 -100 200 -100 50 2 3 3 4 4 5 5 1 2 1
0
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 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
The first thing that comes to mind is to walk all routes by recursion. How many are there from the Almaty-2 station to MEGA? More than 1015. Where in this enumeration is the same work repeated?
2Hint 2
The number of routes from a crossing does not depend on how you got to it. If you know the answers for all neighbours closer to t, the answer for the crossing itself is their sum. In what order should you count so that the neighbours are always ready first?
3The idea
Denote by W(u) the number of routes from u to t. Then W(t) = 1, and for the others W(u) is the sum of W(v) over all pieces of street u–v for which v is closer to t than u. Each term belongs to a crossing with a smaller distance to t, so it is enough to sort the crossings by distance to t and count in increasing order: by the time u is counted, all the needed W(v) are already in the table. This is DP on a graph without cycles.
4Walkthrough
Distances are compared by their squares: (x − xt)² + (y − yt)² is an integer, and the comparison is exact. The square root and floating-point numbers are dangerous here: in the sixth test the squared distances of two neighbouring crossings are 1018 and 1018 − 27, and in a 64-bit floating-point number both round to the same 1018. The comparison “strictly closer” then lies, and one of the two routes disappears.
Loops take no part by themselves: a loop's end is not closer than its start. Two parallel pieces add the sum twice, as required. One can count only while the distance does not exceed the distance from s: farther crossings do not affect the answer. Each cell holds a remainder modulo 109 + 7.
Recursion with memoisation also gives the right numbers, but in the last test the chain of subproblems is 50,000 long: in Python it hits the recursion depth limit, and in Go it needs a large stack. A loop over the sorted order does not depend on depth.
4+Solution
5Complexity
Sorting is O(n log n), the count itself O(n + m): each piece is looked at from both ends. Memory O(n + m).
6Common mistakes
- Enumeration without memory. On Almaty there are more than 1015 routes: you will not see the end of it.
- Counting in the order of crossing numbers or by breadth-first search from t. A neighbour that is closer in a straight line may have a larger number and lie in a more distant layer of the search.
- Distances in floating point. Fails the sixth test.
- Products in 32-bit integers. The difference of coordinates reaches 2·109, its square 4·1018: int64 is needed.