시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB54480.000%

문제

Snake is a polyline with n vertices (without self-intersections). Initially, the coordinates of the i-th vertex of Snake is (xi, yi). Snake can move continuously by translation and rotation, but it can’t change its shape (the lengths of the segments in the polyline and the angles between segments can’t be changed). The line y = 0 is a wall, and there is a small hole at (0, 0). Determine whether Snake can pass though the hole. (Initially, all points on Snake satisfy y > 0. After the movement, all points on Snake should satisfy y < 0.)

입력

First line of the input contains one integer n (2 ≤ n ≤ 1000). Then n lines follow, i’th of them contains pair of integers xi and yi (0 ≤ xi ≤ 109, 1 ≤ yi ≤ 109, (xi, yi) ≠ (xi+1, yi+1)). The polyline doesn’t have self-intersections. No three points are on the same line.

출력

If Snake can pass though the hole, print “Possible”. Otherwise print “Impossible”.

예제 입력 1

4
0 1
1 1
1 2
2 2

예제 출력 1

Possible

예제 입력 2

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

예제 출력 2

Impossible

힌트

For the first example, solution may look in the next way:

  • Move 1 to the −y direction.
  • Rotate 90 degrees coounter-clockwise around the point (0, 0).
  • Move 1 to the −y direction.
  • Rotate 90 degrees clockwise around the point (0, 0).
  • Move 1 to the −y direction.
  • Rotate 90 degrees counter-clockwise around the point (0, 0).
  • Move 2 to the −y direction.