Codeforces Round #549 (Div. 1) C. U2

Draw parabolas satisfying the given condition. Then, an envelope appears *1.

This is similar to the convex hull. Actually, Graham scan *2 also works in this case. There is another solution using the the convex hull of (x[i],y[i]-x[i]*x[i]). This convex hull has the same information.

My submission: https://codeforces.com/contest/1142/submission/52050526
Problem statement: https://codeforces.com/contest/1142/problem/C

*1:This figure is not correct because some parabolas are not drawn. However, I won't fix it. It is enough to understand this phenomenon.

*2:One of algorithms for finding the convex hull.