H - 包囲 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

2次元平面上に存在する格子点のうちN個の格子点は色が塗られている。 色が塗られた格子点のいくつかを選んで、選んだ点たちを頂点とする単純多角形を作る。そのような単純多角形のうち、原点を内部に含み面積が最小のものの面積を求めよ。

ここで単純多角形とは自己交差のない多角形のことである。

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
X_2 Y_2
:
X_N Y_N
  • 1 行目に格子点の数を表す整数N(1 \leq N \leq 200)が与えられる。
  • 1+i 行目にはi番目の格子点の座標(X_i, Y_i)が与えられる。
  • 与えられる格子点は以下の制約を満たす。
  • -100000 \leq X_i, Y_i \leq 100000
  • (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
  • (X_i, Y_i) \neq (0, 0)

出力

  • 原点を内部に含む単純多角形が存在しないならばImpossibleのみを1行に出力せよ。
  • 原点を内部に含む単純多角形が存在するならばPossibleを1行目に出力し、2行目に面積の最小値を出力せよ。
  • 改行を忘れないこと。また、面積については想定解答との絶対誤差または相対誤差が、10^{-8}以下であれば、正解として扱われる。

入力例1

3
-1 -1
1 -1
0 2

出力例1

Possible
3.0000000000

1番目の点と2番目の点と3番目の点をつないだ三角形が原点を内部に含む面積最小の単純多角形である。

入力例2

4
-1 -1
1 -1
1 1
-1 1

出力例2

Possible
4.0000000000

1番目の点と2番目の点と3番目の点と4番目の点をつないだ四角形が原点を内部に含む単純多角形のうち面積が最小のものである。 点をつなぐ順番によっては単純多角形にならないことに注意せよ。

入力例3

3
-1 -1
1 -1
1 1

出力例3

Impossible

1番目の点と2番目の点と3番目の点をつないだ三角形は原点を境界上に含むものの、内部には含んでいないため条件を満たさない。よって原点を内部に含む単純多角形は存在しない。