题目描述

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.

10
10 30 10 90
30 90 10 30
10 30 90 110
30 90 90 110
30 80 40 90
90 120 10 110
120 170 10 50
120 130 60 110
130 170 60 110
130 170 50 60

2
1200

7
0 3 0 24
3 9 0 24
9 15 0 12
9 15 12 24
15 17 0 8
15 17 8 16
15 17 16 24

0
0