> use that extra information to perform MUCH better

Do you mean using a better estimator for the median value? Or something else?

Say, if you know the function is a polynomial of degree N, with N+1 datapoints you can find it – e.g. with Lagrange's polynomial, although the finite precision of computer numbers might make that more complex.