This solution is by the tester yuto1115.

We consider a grid instead of lattice points on a coordinate plane. Let \(M\) be the largest coordinate of a stone.

Divide the cells in \([-1,M+1]\times[-1,M+1]\) without a stone into \((1\times n)\) maximal regions.

Example: an example of division. Black cells represent lattice points with stones.

This way, the entire region is divided into \(O(M+N)\) rectangular regions (or \(O(N)\) regions by coordinate compression). By performing BFS (Breadth-First Search) on these rectangular regions by the adjacency of the rectangle, one can enumerate the rectangular regions reachable from \((-1,-1)\).

By managing the rectangular regions for each row as an ordered set of segments \([L, R]\), adjacent rectangular regions above and below can be enumerated fast. Thus, the answer can be found in a total of \(\tilde{O}(N+M)\) or \(\tilde{O}(N)\) time.