| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 137 | 73 | 61 | 50.413% |
Recently, RUN was asked to connect cables between all pairs of the $N$ areas of KAIST.
We treat the areas as regions on the $2$-dimensional plane. The boundary of each region is a $4$-sided polygon with $2$ edges parallel to the $x$-axis, and $2$ edges parallel to the $y$-axis. In other words, each region has a rectangular boundary with $(x_1^i,y_1^i)$ as a lower left corner and $(x_2^i,y_2^i)$ as a upper right corner. The regions may overlap.
The cables must be constructed along the $x$-axis or the $y$-axis, due to safety issues. So the cost of constructing a cable from $(x_1,y_1)$ to $(x_2,y_2)$ is $\left |x_1-x_2\right |+\left |y_1-y_2\right |$ won.
A cable connecting two areas $A$ and $B$ should connect two points, one from each region.
Find the minimum sum of the cost for connecting $\binom{N}{2}$ cables between all pairs of the areas.
Note that the cables must be constructed for all $\binom{N}{2}$ pairs of areas. This means, for example, even if two endpoints of a cable belong to more than one pair of areas, we do not consider it as connecting all such pairs.
Since the answer can be large, output it modulo $998\, 244\, 353$. It can be proved that the answer is always a non-negative integer.
The first line contains one integer, $N$.
The $i$-th of the following $N$ lines contain space-separated four integers $x_1^i$, $y_1^i$, $x_2^i$, and $y_2^i$ — indicating the positions of the lower left and the upper right corners of the region representing the $i$-th area.
Output a single integer — the minimum cost to construct all cables in the unit of won, modulo $998\, 244\, 353$. $998\, 244\, 353=119\times 2^{23}+1$ is a prime number.
3 1 7 2 9 3 2 8 4 4 3 8 5
8
4 0 1 2 3 1 0 3 2 3 4 5 6 4 3 6 5
8