1
Consider the edges sorted by $f_e(t)$ for some $t$.
Two quadratic polynomials can intersect at most two times. When the cost function of two edges $e_1$ and $e_2$ cross at time $t$, it means that
$f_{e_1}(t-\epsilon) < f_{e_2}(t-\epsilon)$ and
$f_{e_1}(t+\epsilon) > f_{e_2}(t+\epsilon)$.
Since there are $m$ edges and each pair of edges crosses at ...
Only top voted, non community-wiki answers of a minimum length are eligible