← 返回题目列表

AtCoder · joisc2008_origami

origami. 折纸

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

折り紙 (Origami) - 原题 PDF 第 1 页
原题PDF第1页
折り紙 (Origami) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Origami: 折り紙


input ファイル“origami.in”
output 標準出力
ソースファイルorigami.c/origami.cpp
時間制限1 秒/ データ



 あなたはJOI 高校の文化祭の展示のため,貼り絵を作ることになった.

 貼り絵は,台紙にいくつかの折り紙を貼り付け作るのだが,折り紙を重ねて貼ると厚みが出

てはがれやすくなる.そこで折り紙が最も多く重なっている部分が何枚重ねであるのかと,そ

の部分の合計の面積を知りたい.

 まず貼り絵を作るための台紙として,横a cm,縦b cm の長方形の紙を使うことにした.こ

の台紙には1 cm おきに辺に平行になるように縦横に直線が引かれ,全体でa × b 個の一辺1 cm

の正方形の格子ができるように区切られている.これより,左からx 列目,下からy 行目の格

子を(x, y) と表す.





           図1: 横8 cm,縦6 cm の長方形の台紙(a = 8, b = 6 の場合)



 次に,台紙の上にn 枚の長方形の折り紙を順番に貼っていく.折り紙の貼り方(折り紙を貼る

位置) は,4 つの整数の組(p, q, r, s) で指定される.p, q, r, s は


                            1 ≦p ≦r ≦a,  1 ≦q ≦s ≦b


をみたす整数である.これは横(r −p + 1) cm × 縦(s −q + 1) cm の長方形の折り紙を,4 つ

の格子(p, q), (p, s), (r, q), (r, s) が折り紙の角になるように,台紙の上に貼ることを意味する.

 下の図は,横8 cm,縦6 cm の長方形の台紙に,4枚の折り紙を(2, 4, 3, 6), (5, 1, 6, 6), (2, 5, 8, 5),

(1, 2, 5, 3) の順番に貼った様子を図示したものである.このとき最も多く折り紙を重ねている部
分は2 枚重ねであり,その部分の合計の面積は6cm2 である.



                          折り紙–1/2

図2: 貼付け方の例


 入力として台紙の大きさと,台紙に貼る折り紙の貼り方が与えられたとき,最も多く折り紙

が重なっている部分は何重であるかと,その部分の面積を求めるプログラムを書け.ただし,入

力では,必ず2 枚以上の紙が重なっている格子が存在する.

Input.  入力ファイルorigami.in の1 行目には台紙に貼る折り紙の枚数を表す整数n  (1 ≦

n ≦5, 000) が書かれている.

  2 行目には台紙の大きさを表す整数a, b (1 ≦a, b ≦1, 000, 000) が横,縦の順に書かれている.

   i + 2 行目(1 ≦i ≦n) には,i 枚目の折り紙の貼り方を表す4 つの整数pi, qi, ri, si が書かれ

ている.pi, qi, ri, si は

           1 ≦pi ≦ri ≦a,    1 ≦qi ≦si ≦b,      ri −pi < 20,      si −qi < 20

を満たす.すなわち,貼り絵に用いる折り紙の辺の長さは20 cm 以下である.


Output. 出力は標準出力に2 行で出力する.

  1 行目には最も多く折り紙が重なっている部分は何重に貼られているかを表す整数を,2 行目
には最も沢山の折り紙が重なっている部分の面積を表す正の整数(単位はcm2) を出力せよ.

採点基準採点に用いる入力データのうち,20%分はn ≦20, 1 ≦a, b ≦50 を満たす.また,そ

れとは別の20%分はn ≦100 を満たす.


例

次の例は図2 の場合である.

 origami.in 標準出力
 4           2
 8 6         6
 2 4 3 6
 5 1 6 6
 2 5 8 5
 1 2 5 3



                          折り紙–2/2