← 返回题目列表

AtCoder · ttpc2015_h

H. 围攻

中文机器翻译题面 查看原题

問題文

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个点的三角形在其边界上包含原点,但不满足条件,因为它内部不包含原点。因此,不存在包含原点的简单多边形。 大于或等于