P15769 [JAG 2025 Summer Camp #2] Strange House

As a strange house inspector you are inspecting a house consisting of $n$ rooms. Each room is a rectangle in the $xy$-plane, and each of its edges is parallel to the $x$- or $y$-axis. Two rooms can touch but do not overlap. Let us say that two rooms are adjacent if their borders share a segment of a positive length. It is guaranteed that one can reach from any of the rooms to any other room by repeatedly moving to an adjacent room. In addition, if the borders of two rooms share only a single point, there is another room which is adjacent to both rooms. Figure D-1 depicts the Sample Input 1. On the other hand, Figures D-2 and D-3 are invalid inputs. :::align{center}  ::: In Figure D-1 you may have found strange spaces surrounded by rooms. More precisely, a simple polygon is called a **strange space** if the following conditions are satisfied. - The polygon and any room do not overlap. - For any point on the border of the polygon, there is a room whose border contains that point. Your task is to find all the strange spaces of the house. Output the number of strange spaces and the sum of their areas.

The input consists of a single test case of the following format. $$ \begin{aligned} & n \\ & l_1 \ r_1 \ b_1 \ t_1 \\ & \vdots \\ & l_n \ r_n \ b_n \ t_n \end{aligned} $$ The first line contains an integer $n$ ($1 \leq n \leq 200\,000$) representing the number of rooms in the house. Each of the following $n$ lines contains four integers satisfying $0 \leq l_i < r_i \leq 10^9$ and $0 \leq b_i < t_i \leq 10^9$. Each line represents that corners of the $i$-th room are $(l_i, b_i)$, $(r_i, b_i)$, $(r_i, t_i)$ and $(l_i, t_i)$. These rooms satisfy all the conditions explained in the problem statement.

Output two lines. The first line should contain the number of strange spaces of the house. The second line should contain the sum of areas of these strange spaces.