G: 最小包含矩形 - Minimum Enclosing Rectangle -

物語

みんなぁ、こんにちは！　八森中ぷろこん部の藍座あいりだよぉ。 突然だけど、あいりがこの前解けなかった問題をみんなに解いて欲しいんだぁ～。 この前部活でICPC2010のA問題を解いたんだけど、その時の問題が難しかったんだぁ。

あ、ICPCについて説明しなきゃ！　ICPCは、い、いんたーなしょなる……ちゅうがくせい……ぷろぐらみんぐ……こんてすとの略で、日本語に直すと、国際中学生対抗プログラミングコンテストらしいよぉ！ あいりにはちょっとむずかしい言葉がいっぱいだよぉ。 あいり達はこの世界大会に出るために毎日頑張ってるんだぁ！

部活から帰った後お姉ちゃんにも聞いてみたんだけど、「わ、わからないわ……A問題からわからないなんて……お姉ちゃん失格ね……」って落ち込んじゃって…… でも、「『プロ』の人たちが一杯集まるところを知ってるの、お姉ちゃんちょっと連絡してみるわ。あいり、そこで聞いてみなさい！」って言ってここの合宿を教えてもらったんだぁ～ 。 ここに集まる『プロ』のみんなには簡単かもしれないけど……この問題を解いてほしいの！

問題

長さが1の正方形がN個、2次元平面上にある。これらN個の正方形を全て内包する、最小面積の長方形を求めよ。

入力形式

入力はN行からなる。

N
n_1 d_1
n_2 d_2
n_3 d_3
...
n_{N − 1} d_{N − 1}

最初の行には、正方形の個数Nが与えられる。 以下N − 1行は、正方形の置き方を表している。そのうち上からi行目は、空白区切りで1つの整数n_{i}と1つの文字d_{i}が与えられる。これはi番目の正方形の置き方を指示している。ここで正方形の番号付けは、最初の正方形を0番目とし、その後置いた順番に1, 2, ..., N − 1と番号付けられるものとする。0番目の正方形に対する置き方の指示はない。 i番目の正方形に対する置き方の指示n_i, d_iは、i番目の正方形をn_i番目の正方形に対してd_iで示される方向に隣接して置くことを指示する。 ここで、n_iはi未満の非負整数である。また、d_iは0,1,2,3のいずれかの値をとり、それぞれd_iの値が、0ならば左側、1ならば下側、2ならば右側、3ならば上側を表す。 以下にそれぞれの入力例に対応した最終的な正方形の配置を図示している。左から入力例1、入力例2、入力例3、入力例4の最終的な正方形の配置となっている。図中の番号は正方形の番号に相当する。また、図中の緑線は求める最小面積の長方形を示している。

制約

• 入力はすべて整数
• 1 ≤ N ≤ 100,000
• 1 ≤ n_i < i (1 ≤ i < N)
• 0 ≤ d_i ≤ 3 (1 ≤ i < N)
• 既に正方形が置かれている位置に、新たな正方形を置くような指示は与えられない。

出力形式

与えられたN個の点を全て包含する最小面積の長方形の面積を1行で出力する。 出力には10^{−5}以上の誤差を含んではならない。

入力例1

1

出力例1

1

入力例2

5
0 0
0 1
0 2
0 3

出力例2

8

入力例3

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

出力例3

16

入力例4

10
0 2
1 2
2 2
3 2
2 1
5 1
6 1
7 1
8 1

出力例4

30

Note

Link

 

---