First we need to sort by x-coordinate and then by y-coordinate in order to find for each nail its neighbour in each of the four directions.

Now we simulate the removing of nails in order to find the order of removal.

Then we retrace our steps. Starting with the remaining two nails we add back nails, keeping track of the convex hull and calculating its area.

We can keep track of four extreme nails on the hull – top, bottom, left and right. This is helpful because they divide the hull into four parts in which the hull behaves predictably and adding a nail is simple.

Because of the way we removed nails, every nail we add will become extreme. After adding a nail, we remove nails near it until the hull is convex again, calculating the change in area along the way.