A navigator without trigonometry
A route is a polyline of n points P1, …, Pn. At each interior point Pi the direction changes: we enter along the vector u = Pi − Pi−1 and leave along the vector w = Pi+1 − Pi. Let θ be the turn angle from u to w, from −180° to 180°. The navigator says:
- nothing if |θ| ≤ 45°;
leftorrightif 45° < |θ| < 135°;sharp leftorsharp rightif 135° ≤ |θ| < 180°;u-turnif |θ| = 180°: the road turned exactly back.
Left is anticlockwise, with the y axis pointing up. The boundaries are exact: a turn of exactly 45° is still “straight”, a turn of exactly 135° is already “sharp”. Coordinates go up to a billion, and the answer must be right even for a turn that differs from 45° by a billionth of a degree.
The second and third tests are a courier’s routes through the streets of Almaty from OpenStreetMap, with coordinates in decimetres.
Input
The first line holds n (2 ≤ n ≤ 30,000), then come n lines with integer coordinates x, y (|x|, |y| ≤ 10⁹). Neighbouring points are distinct.
Output
The first line holds the number of prompts k. Then k lines in route order: the number of the point (points are numbered from one) and the prompt.
Examples
Example 1
8 0 0 4 0 8 4 4 8 4 2 4 9 10 9 16 10
4 3 left 4 sharp left 5 u-turn 6 right
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 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
The angle is not needed here. Compare what the cross and dot products say about θ, and express the condition “|θ| ≤ 45°” through them, without sines or arctangents.
2The idea
The cross product c = u × w = |u||w| sin θ, the dot product d = u · w = |u||w| cos θ. The factor |u||w| is positive and the same, so c and d themselves can be compared as if they were the sine and cosine.
- |θ| ≤ 45° ⇔ cos θ ≥ |sin θ| ⇔ d > 0 and |c| ≤ d.
- |θ| ≥ 135° ⇔ −cos θ ≥ |sin θ| ⇔ d < 0 and |c| ≤ −d.
- |θ| = 180° ⇔ c = 0 and d < 0.
- The side of the turn is given by the sign of c.
All the quantities are integers, the comparisons are exact, and the 45° boundary runs exactly where the statement says.
3Walkthrough
Check in this order: first the U-turn, then “straight”, then “sharp”, otherwise an ordinary turn. The order matters: a U-turn also satisfies the condition “|c| ≤ −d”, but it has its own prompt.
Why not atan2? It almost always gives the right answer, but the fifth test is made of turns that differ from 45° and 135° by a minute amount: |c| and d differ by one at values around 10¹⁷. A double holds 15–16 significant digits, and in the conversion that one is lost. Such pairs of vectors are easy to build: one has to solve the equation |c| − d = ±1 in integers, and it is a linear equation in the coordinates of w, solved by the extended Euclidean algorithm. That is how the test generator works.
There is no overflow: coordinate differences up to 2·10⁹, products up to 4·10¹⁸, c and d up to 8·10¹⁸ fit in int64. The absolute value |c| is safe too: −8·10¹⁸ changes sign without overflow.
3+Solution
4Complexity
O(n): a few multiplications per point.
5Common mistakes
- The angle through atan2 or arccos. Passes all the tests except the fifth, where the turns sit right on the boundary.
- “<” instead of “≤”. A turn of exactly 45° is “straight”. In the example it is the second point of the route.
- A U-turn as “sharp”. At θ = 180° the cross product is zero, and the sign of the side is undefined; it is a separate prompt.
- Normalising the vectors. Dividing by the lengths gives fractions and roots, and they are not needed for a comparison: a common positive factor does not affect signs and comparisons.