Sheets

Time Limit : 5 sec, Memory Limit : 65536 KB

平面に長方形のシートが何枚か置かれている. これらのシートで覆われている部分の面積や周長を求めるプログラムを作成せよ.

ただし, 平面を座標平面とみなしたとき, シートの配置は次の条件 (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

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Notes on Submission

標準入出力を行うプログラムを作成して下さい。

上記の形式で複数のデータセットが与えられます。n, r が0のとき入力が終了します。

Sample Input

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

Sample Output

29
29
38
80
36
45
36

Source: 5th Japanese Olympiad in Informatics , 2006-02-12
http://www.ioi-jp.org/