0905 - 魔女っ娘ヒナくるん -Magic.06

Magic.06 『Brain Muscle』

前回のあらすじ

アヤの広報によって、幻想郷中にその名が知れ渡ったヒナくるん。

そんなある日、ヒナくるんの元にある情報が入ってきたのだった。

本編

ヒナくるん

「怪しい格好をした河童が地底に入っていったですって？」

アヤ

「そうよ。哨戒中の天狗仲間から得た情報だから間違いないわ。」

ヒナくるん

「放っておくのも危険そうね。準備して早速向かいましょう！！」

アヤ

「それが・・・地底への穴が無くなってしまったらしいの。

　恐らく光学迷彩で隠されてるのだろうけど、

　見つけることができない分探すだけで大変よ。」

ヒナくるん

「もしかしたら入り口の場所を知ってる妖怪達がいるかもしれないわ！！

　まずは聞き込みから始めてみましょう！！」

問題

地底を訪れたことのないヒナくるんは、

聞き込みにより入り口を特定する方法を提案した。

聞き込みでは、幻想郷を縦横のグリッドに分割し、

どの範囲内で入り口で見たかの記憶を聞く。

「X=0から5,Y=2から3の範囲内で入り口を目撃した。」のような具合である。

ヒナくるんの家を(X=0,Y=0)とする。

ヒナくるんは聞き込みを終えた後、得た情報を元に入り口を探す。

最悪の場合として最後の座標を確認するまで入り口が見つからない場合があるので、

得た情報を用いて探索する範囲を可能な限り狭めたい。

ヒナくるんとアヤが聞き込みをした回数と、

各聞き込みで得た情報が与えられるので、

ヒナくるんとアヤは最悪何個の座標を確認する必要があるかを出力せよ。

この問題に対して、放送事故 が起こることはない。

入出力形式

一行目に、ヒナくるん達が聞き込みをした回数 N が与えられる。

続いてN行に渡り、地底への入り口を見た座標の範囲、

sx , sy , gx , gy が空白区切りで与えられる。

この入力は、「X座標sxからgx , Y座標syからgy内に地底への入り口がある」ことを示す。

N
sx1 sy1 gx1 gy1
sx2 sy2 gx2 gy2
..
..
sxN syN gxN gyN

全ての聞き込みを終えた後、

ヒナくるん達が探索する座標の数を改行込みで出力せよ。

制約

• 1 ≦ N ≦ 1000000
• -100000000 ≦ sx,sy,gx,gy ≦ 100000000
• sx ≦ gx
• sy ≦ gy
• 地底への入り口は一つであり、偽の情報が与えられることはない。

入出力例

入力例

3
-8 -1 9 2
-9 1 1 9
-1 1 9 4

出力例

6

この例では、

「X=-1から1 Y=1から2の範囲」まで絞ることができるため、

探す必要のある座標数の最大は6である。