時間制限:1000ミリ秒
メモリ制限:65536KB
問題
ディックとの日帰り旅行の後、ハリーは彼のスポーツ用多目的車のドアに複数の小さな穴があることに気づいた。地元のタイヤ店では、ドアの上から貼って修理に用いるプラスチックシートを正方形の形でのみ販売している。ハリーがドアを修理するのに必要なプラスチックシートの面積はどのくらいなのだろうか?
小さな穴は平面の整数格子点上にあることを仮定してよい。あなたの仕事は全ての穴を覆う最小の正方形の面積を求めることである。
入力
一行目にテストケース数Tが与えられる。
各テストケースは一行目に点の個数Nが与えられる。続くN行に、各点のx座標とy座標が与えられる。全ての入力の数値は先頭に余計な0を含まない10進整数で与えられる。
テストケースは30個以下であり、Nが30を超えるテストケースはない。各点の座標は原点(0,0)から500単位距離離れることはない。
出力
一行に小数点以下2桁の精度で、全ての点を覆うのに必要な最小の正方形の面積を出力せよ。
入力例
2 4 -1 -1 1 -1 1 1 -1 1 4 10 1 10 -1 -10 1 -10 -1
出力例
4.00 242.00
出典
Waterloo Local Contest, 2007.7.14