AT_joisc2008_origami.折り紙 (Origami)

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

今天,我们要制作一幅贴画。

贴画是将几个贴纸贴在一块底板上,如果把贴纸叠在一起贴,就会显得很厚,容易脱落。为了防止这种情况的出现,我们想要知道贴纸重叠最多的部分是几张重叠,以及这些部分合计的总面积。

制作贴画的底板是一个宽 aa 厘米、长 bb 厘米的长方形纸张。这张底纸每隔 1cm1 \text{cm} 画一条与边平行的纵横直线,整体被划分成 a×ba \times b 个边长 1cm1 \text{cm} 的正方形小格,从左起第 xx 列和从下起第 yy 行的格子表示为 (x,y)(x, y)。

在底板上按顺序贴上 nn 张长方形的贴纸,贴纸的粘贴方法(粘贴贴纸的位置)由一个四元组 (p,q,r,s)(p,q,r,s) 指定。

它的意思是把 (r−p+1) cm×(s−q+1) cm(r-p+1) \ \text{cm} \times (s - q + 1)\ \text{cm} 的长方形折纸,将四个格子 (p,q),(p,s),(r,q),(r,s)(p,q),(p,s),(r,q), (r,s) 作为贴纸的角贴在底板上。

下图示意了在宽 8 cm8\ \text{cm}、长 6 cm6 \ \text{cm} 的长方形底板上,将四张贴纸按照 (2,4,3,6),(5,1,6,6),(2,5,8,5),(1,2,5,3)(2,4,3,6),(5,1,6,6),(2,5,8,5),(1,2,5,3) 的顺序贴上。此时贴纸重叠最多的部分是两张重叠,该部分合计的面积为 6 cm26\ \text{cm}^2。

示意图

现在你需要写程序求出折纸重叠最多的部分是几层,并求出该部分的面积。保证输入一定存在有两张以上纸张重叠的格子。

输入格式

输入共有多行。

第一行,一个整数 nn,代表贴纸的数量;

第二行,两个整数 a,ba,b,含义如题所示;

第 33 行到第 n+2n+2 行,每行四个整数,第 ii 行的四个整数分别表示 pi,qi,ri,sip_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%100\% 的数据,保证 1≤n≤5000,1≤a,b≤106,1≤pi≤ri≤a,1≤qi≤si≤b,ri−pi<20,si−qi<201 \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。

输入解题思路,AI测评打分。不知道怎么写?

首页