Snake

Time Limit : 2 sec, Memory Limit : 262144 KB

すなけ君は,(自己交差を持たない) n 個の頂点からなる折れ線の形をしている.最初に,すなけ君の i 番目の頂点は (xi, yi) にある.すなけ君は,平行移動や回転をして連続的に移動することはできるが,変形(折れ線の長さや二つの線分のなす角度を変える) することはできない.y = 0 は壁であり,(0, 0) に微小な穴が開いている.すなけ君がこの穴を通って全体が y < 0 をみたすように移動できるかどうか判定せよ.

Constraints

  • 2 ≤ n ≤ 1000
  • 0 ≤ xi ≤ 109
  • 1 ≤ yi ≤ 109
  • 折れ線は自己交差を持たない
  • どの三点も同一直線上にない
  • (xi, yi) ≠ (xi+1, yi+1)
  • 入力は全て整数である

Input

n
x1 y1
. . .
xn yn

Output

すなけ君が穴を通って移動できる場合は"Possible", できない場合は"Impossible" と出力せよ.

Sample Input 1

4
0 1
1 1
1 2
2 2
Sunake

Sample Output 1

Possible
  • y 方向に 1 平行移動する.
  • (0, 0) を中心として 90 度反時計回りに回転する.
  • y 方向に 1 平行移動する.
  • (0, 0) を中心として 90 度時計回りに回転する.
  • y 方向に 1 平行移動する.
  • (0, 0) を中心として 90 度反時計回りに回転する.
  • y 方向に 2 平行移動する.

Sample Input 2

11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 141
19 124
0 156
22 183

Sample Output 2

Impossible

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 2, Tokyo, Japan, 2014-09-13
http://acm-icpc.aitea.net/
http://jag2014summer-day2.contest.atcoder.jp/