AT_joisc2008_origami 折り紙 (Origami)

题目描述

今天,我们要制作一幅贴画。 贴画是将几个贴纸贴在一块底板上,如果把贴纸叠在一起贴,就会显得很厚,容易脱落。为了防止这种情况的出现,我们想要知道贴纸重叠最多的部分是几张重叠,以及这些部分合计的总面积。 制作贴画的底板是一个宽 $a$ 厘米、长 $b$ 厘米的长方形纸张。这张底纸每隔 $1 \text{cm}$ 画一条与边平行的纵横直线,整体被划分成 $a \times b$ 个边长 $1 \text{cm}$ 的正方形小格,从左起第 $x$ 列和从下起第 $y$ 行的格子表示为 $(x, y)$。 在底板上按顺序贴上 $n$ 张长方形的贴纸,贴纸的粘贴方法(粘贴贴纸的位置)由一个四元组 $(p,q,r,s)$ 指定。 它的意思是把 $(r-p+1) \ \text{cm} \times (s - q + 1)\ \text{cm}$ 的长方形折纸,将四个格子 $(p,q),(p,s),(r,q), (r,s)$ 作为贴纸的角贴在底板上。 下图示意了在宽 $8\ \text{cm}$、长 $6 \ \text{cm}$ 的长方形底板上,将四张贴纸按照 $(2,4,3,6),(5,1,6,6),(2,5,8,5),(1,2,5,3)$ 的顺序贴上。此时贴纸重叠最多的部分是两张重叠,该部分合计的面积为 $6\ \text{cm}^2$。 ![示意图](https://cdn.luogu.com.cn/upload/image_hosting/71q77404.png) 现在你需要写程序求出折纸重叠最多的部分是几层,并求出该部分的面积。保证输入一定存在有两张以上纸张重叠的格子。

输入格式

输入共有多行。 第一行,一个整数 $n$,代表贴纸的数量; 第二行,两个整数 $a,b$,含义如题所示; 第 $3$ 行到第 $n+2$ 行,每行四个整数,第 $i$ 行的四个整数分别表示 $p_i,q_i,r_i,s_i$。

输出格式

输出共两行。 第一行,一个整数,代表贴纸重叠最多的部分的重叠层数; 第二行,一个整数,代表这部分的面积。 ### 样例 #1 #### 样例输入 #1 ``` 4 8 6 2 4 3 6 5 1 6 6 2 5 8 5 1 2 5 3 ``` #### 样例输出 #1 ``` 2 6 ```

说明/提示

对于 $100\%$ 的数据,保证 $1 \leq n \leq 5000,1 \leq a,b \leq 10^6,1 \leq p_i \leq r_i \leq a,1 \leq q_i \leq s_i \leq b,r_i-p_i < 20,s_i-q_i< 20$。