We will share an \(O(N)\) solution, which can be derived from the official editorial with some more considerations. As in the official editorial, we only need to check

1. vertexes in the lower hull
2. edges in the lower hull

For 2., we only need to check the edge which is between \(x>y\) area (call A zone hereafter) and \(x<y\) area (call B zone). We have at most one edge connecting A and B zones. Classify vertexes in a similar way to A group and B group, depending on which zone they are on. For each group, find the vertex with the smallest \(x+y\) value. We now know that at least one of two these vertexes are to be chosen (Hint for the proof: slope of the edge connecting A and B is greater than \(-1\) or not. Check both cases).

We don’t need to construct the lower full. For 1., we can simply check all \(N\) vertexes. For 2., check all the pairs which contains at least one of two special vertexes. All the processes can be done in \(O(N)\) time.

AC code （PyPy3）