If we regard each pillar as a vertex and each beam as an edge, then we obtain a simple plane bipartite graph \(G\). Let \(N, M, F\) be the numbers of vertices, edges, and faces, respectively, of \(G\). Then, Euler’s polyhedron formula

\[N - M + F = 2\]

implies \(M \le 2N - 4\). This is because the boundary of each face of \(G\) is formed by at least \(4\) edges, each edge appears in a boundary at most twice, and hence we can conclude \(4F \le 2M\).

This upper bound is always achievable. Starting with the rectangle with the four corners, we can recursively repeat the following operation: pick a grid point in the inside of a quadrilateral and stretch two segments to the picked point from one pair of the diagonal points of the quadrilateral. Note that we can choose at least one pair so that the new segments do not intersect any of the existing segments. By this operation, two segments can be added per one internal grid point. As we initially have \(N = 4, M = 4\), we finally attain \(M = 2N - 4\), which is optimal.

If we randomly choose an internal grid point every time, then, like the quick sort, it is expected that we can design a divide-and-conquer algorithm which runs in expected \(\mathrm{O}(N \log N)\) time, and this is true in practice. However, the writer could not prove it so far. (If you can do it, we are very happy to hear that.)

If we consider a deterministic algorithm as below, we can obtain a theoretical bound of the computational time. First, divide the rectangle by the diagonal line between the upper-left corner and the lower-right corner. In each triangular area, process the internal grid points in the ascending order of the distance from this line. Then, each processed point is guaranteed to be in a quadrilateral one of whose corners is the upper-right (or lower-left) corner of DEGwer’s land. By maintaining such quadrilaterals by a binary search tree, we can find which quadrilateral contains the processed point in \(\mathrm{O}(\log N)\) time, and thus all we have to do are done in \(\mathrm{O}(N \log N)\) time in total.

Digression

The judge program is also required to run in \(\mathrm{O}(N \log N)\) time. (ABC-G(Ex)?)