Near and Far Deliveries

A delivery firm wants the simplest useful forecast: "deliveries up to t km take left minutes, longer ones take right minutes". From a log of km[i] (distance) and minutes[i] (time taken) it wants the rule with the smallest sum of squared errors (SSE) on the log.

The thresholds considered are the midpoints (a + b) / 2 of every two neighbouring distinct distances a < b in the log; a delivery at distance d is "near" if d < t and "far" otherwise. For a threshold, left and right may be any numbers.

Write split_fit(km, minutes) that returns a tuple (t, left, right, sse) for the best rule, with left, right and sse as floats. Let m be the smallest SSE of any threshold: return the smallest threshold whose SSE is at most m + 1e-6.

The tests use delivery_log(n, seed), which returns (km, minutes); it is available in your code. The logs have up to 20,000 deliveries with over a thousand distinct distances.

Examples

Input:  km = [2.5, 1.0, 4.0, 3.0], minutes = [14, 10, 30, 13]
Output: (3.5, 12.333333333333334, 30.0, 8.666666666666666)
Explanation: near deliveries (10, 14 and 13 minutes) are best predicted by their mean, 12.33;
their squared errors add up to 8.67. The single far delivery is predicted exactly.

Input:  km = [1, 2, 3], minutes = [5, 1, 5]
Output: (1.5, 5.0, 3.0, 8.0)
Explanation: the thresholds 1.5 and 2.5 both give an SSE of 8; the smaller one wins.

Constraints

• 2 <= len(km) <= 20000, with at least two distinct distances
• distances have at most two decimals; minutes are whole numbers from 1 to 1000

Goals

• Learn a two-constant regression rule by minimising the squared error over every split
• Use the fact that the best constant on each side is that side's mean
• Compute every split's error in one sorted pass with running sums