Keep the fewest keyframes from a recorded drag

A motion editor records an element's position at every frame while you drag it. Saving every sample makes the animation file large, so the editor keeps only some samples as keyframes and plays straight lines between them.

Write fewest_keyframes(times, values, tolerance) that returns the smallest number of samples the editor has to keep.

Input and output:

• times: 1 to 1,000 sample times in milliseconds, strictly increasing integers from 0 to 1,000,000.
• values: the recorded position at each time, integers from -1,000,000 to 1,000,000.
• tolerance: an integer from 0 to 1,000,000.
• Returns an integer.

Rules:

• The first and the last sample are always kept.
• Between 2 kept samples with none kept in between, playback follows the straight line through those 2 samples.
• Every sample that is not kept must be within tolerance of that line at its own time. Its distance from the line, measured along the value axis, may equal tolerance but not exceed it.
• Return the smallest number of kept samples that meets these rules.