Newton's method in optimization http://en.wikipedia.org/wiki/Newton's_method_in_optimization http://en.wikipedia.org/wiki/Newton's_method_in_optimization

The same problem was in ch24 qualifying round some years ago. There is another nice way to solve it using hill climbing optimization. You can start from the point (X_s = avg{X_i}, Y_s = avg{Y_i}) and then try to move in each of the 8 directions by some distance d = 10¹⁰ and see which point has the best result out of eight and then you repeat the move but with a smaller distnace d = d / 10. Once d reaches some convergence threshold, 1e - 9 for example, you can output the solution.

I will give it a shot using 2D ternary search, though it is often hard to prove correctness in similar solutions... It is nice to see gradient and hessian applied in some algos :).