← 返回题目列表

AtCoder · joi2006ho_e

E. JOI 2006年最终问题5

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

JOI 2006 本選 問題5 - 原题 PDF 第 1 页
原题PDF第1页
可复制的 PDF 提取文本
5    平面に長方形のシートが何枚か置かれている. これらのシートで覆われて

いる部分の面積や周長を求めるプログラムを作成せよ.

 ただし,平面を座標平面とみなしたとき, シートの配置は次の条件(1), (2) を満

たすものとする.


  (1) 各シートの長方形の4 頂点のx, y 座標は全て0 以上10000 以下の整数であり,

   長方形の各辺はx 軸, またはy 軸に平行である.

  (2) シートの枚数は高々10000 枚以下である.


 入力ファイルのファイル名は“input.txt” である.“input.txt” の1 行目に長方

形の個数n と問題の種類を表す整数r が空白で区切って書かれている. 2 行目以

降の各行には, 各シートの左下頂点座標(x1, y1) と右上頂点座標(x2, y2) の座標値が

x1, y1, x2, y2 の順で空白で区切って書いてある.

出力ファイルのファイル名は“output.txt” である.“output.txt” にはr = 1 のと

き1 行目に面積を, r = 2 のとき1 行目に面積, 2 行目に周囲の長さを出力する. い

ずれの場合も最後に改行を入れること.

 また, テストデータの40% では長方形の頂点の座標が0 以上100 以下で, そのう

ちの1/2 では面積だけを求める問題である. さらに, 全体の1/2 は面積だけを求め

る問題である.


入力例1  入力例2  入力例3  入力例4

5 1       5 2       2 2       3 2

0 0 3 2   0 0 3 2   0 0 8 9   2 2 8 8

1 1 2 5   1 1 2 5   0 0 9 8   3 0 4 9

0 4 6 5   0 4 6 5             5 0 7 9

3 3 5 6   3 3 5 6

5 0 7 6   5 0 7 6


出力例1  出力例2  出力例3  出力例4

29        29        80        45

          38        36        36




                        問題5-1