Snake

시간 제한1초메모리 제한512 MB

요약
모양이 고정된 꺾은선 뱀이 원점의 작은 구멍을 지나 위쪽 반평면에서 아래쪽 반평면으로 이동할 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
기하, 구현
정답자
아직 제출이 없습니다

문제

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”.

힌트

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.

예제2

  1. 예제 1

    입력
    4
0 1
1 1
1 2
2 2
    예상 출력
    Possible

  2. 예제 2

    입력
    11
63 106
87 143
102 132
115 169
74 145
41 177
56 130
28 141
19 124
0 156
22 183
    예상 출력
    Impossible