The longest throw
A coach simulates throws on a computer: a shot, a tennis ball, a feathered shuttlecock. For each projectile the release speed, the release height and how strongly air brakes it are known. We need to find out how far the projectile can be thrown at the best angle. There is no formula for range with air resistance, and each throw is simulated step by step; this is expensive, and the angle must be found in a small number of flights.
A flight at an angle θ degrees to the horizontal with speed v, release height h and terminal velocity vt is computed like this, exactly as in the article’s listing. Let g = 9.81, the step d = 0.002 s, k = g / vt2, and for vt = 0 (a throw in a vacuum) k = 0. The acceleration at velocity (vx, vy) is a(vx, vy) = (−k·s·vx, −g − k·s·vy), where s = √(vx2 + vy2). At the start x = 0, y = h, vx = v·cos θ, vy = v·sin θ. A step of the Runge–Kutta method:
- a1 = a(v), v2 = v + a1·d/2, a2 = a(v2), v3 = v + a2·d/2, a3 = a(v3), v4 = v + a3·d, a4 = a(v4), for each coordinate separately;
- the new position: x′ = x + d·(vx + 2v2x + 2v3x + v4x)/6, and likewise y′;
- if y′ < 0, the projectile has landed, and the range is x + (x′ − x)·y / (y − y′);
- otherwise the new velocity: vx += d·(a1x + 2a2x + 2a3x + a4x)/6, likewise vy, and the position becomes (x′, y′).
The range as a function of angle on [0°, 90°] strictly increases up to the peak and strictly decreases after it. One caveat: at h = 0 and very small angles the projectile goes below ground on the very first step, and the range is zero; on this short stretch the function has a plateau. One flight is up to four thousand steps.
Input
The first line holds the number of projectiles q (1 ≤ q ≤ 20). Then q lines v h vt: the release speed in m/s (1 ≤ v ≤ 50), the release height in metres (0 ≤ h ≤ 3) and the terminal velocity in m/s (vt = 0 or 1 ≤ vt ≤ 200). Numbers are given with at most two decimal places.
Output
q lines: the greatest range of each projectile in metres. An answer is accepted if its relative error is at most 10−6 (absolute for ranges under a metre).
Examples
Example 1
4 13.5 2.1 0 13.5 2.1 149 30 1 21.1 50 1 6.8
20.571066 20.443074 40.927930 12.489273
Example 2
2 10 0 0 10 0 10
10.193678 6.051037
Limits
- Time · Python
- 10000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 8 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
Trying angles in steps of a hundredth of a degree is nine thousand flights per projectile, several thousand steps each. Trying whole degrees is fast, but the peak lies between them. How precisely is the angle needed for the range to agree to a millionth?
2Hint 2
The main thing about the function is known: before the peak it increases, after it decreases. What can be said about the peak if the ranges at two angles are compared?
3The idea
This is the search for the peak of a unimodal function from the article. Two points inside the interval: if the projectile thrown at the larger angle flies further, the peak is right of the smaller angle, otherwise left of the larger one. Each step throws away part of the interval, and a few dozen flights suffice for the required precision. The golden section spends one flight per step, not two: one of the points carries over to the next step with its range.
4Walkthrough
The flight is written exactly as in the statement; the order of operations is the same as in the article’s listing, and the result will agree to the last digits. The search runs on [0°, 90°] down to a width of 10−3 degrees, and the answer is the largest of the ranges computed at the last points.
Why this precision is enough. Near the peak the range behaves like R − c·δ2, where δ is the angle deviation in radians and c is of the order of twice the range: for a throw in a vacuum from the ground R(θ) = v2 sin 2θ / g, and a deviation of δ from 45° reduces the range by a factor of cos 2δ ≈ 1 − 2δ2. At δ ≈ 10−5 radians (a thousandth of a degree is less than two hundred-thousandths of a radian) the relative error is of order 10−9, with a huge margin. This is exactly the square root of precision the article talks about: the range converges twice as fast as the angle.
The plateau at h = 0 does not hinder the search: it is right next to zero, where the range is smallest, and the search points start near 34° and 56° and approach zero only if the peak is there.
4+Solution
5Complexity
The golden section takes 26 flights per projectile, ternary search about sixty, with O(T/d) steps per flight, where T is the flight time. The reference solution in Python passes the heaviest test in about a second.
6Common mistakes
- Whole degrees. 91 flights per projectile, fast, but the best whole angle is up to half a degree off the true one, and the range loses millimetres, more than the allowed error. This is
wrong.py; it is wrong already on the first example. - A fine grid. A step of a quarter of a degree is almost exact, but that is 361 flights per projectile, and Python does not fit in the time. To be sure of meeting the tolerance with a grid, a step under a tenth of a degree is needed: a thousand flights.
- The vacuum formula. tan θ = v / √(v2 + 2gh) holds only without air. The tennis ball from the article is better thrown at 38°, not at 44.7° as the formula says, and the shuttlecock at 24°.
- A different flight step. A step of 0.01 s instead of 0.002 shifts the tennis ball’s range by 0.06 mm, which is already enough to go outside the tolerance, and the Euler method instead of Runge–Kutta by 7 mm.
Algorithms behind it
O(log(L/ε)) function evaluations
2 problems
NUM~
Algorithm
The Euler and Runge–Kutta methods
Step by step along the law of motion: Euler, RK4, the adaptive step, Verlet for orbits and implicit schemes.
O(T/h) steps, RK4 has four evaluations of the right-hand side per step
2 problems