시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 5 | 4 | 4 | 80.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”.
4 0 1 1 1 1 2 2 2
Possible
11 63 106 87 143 102 132 115 169 74 145 41 177 56 130 28 141 19 124 0 156 22 183
Impossible
For the first example, solution may look in the next way: