P4393 New Snake
描述
New Snake是一个新型物种,它的身体是由N个点和N-1条线段构成的折线,其中第i个点的坐标为(xi, yi),折线不会自交。New Snake可以平移或旋转自己的身体,但是在移动过程中,身体形状不能发生任何改变(即构成它身体的每条线段的长度和它们之间的夹角都保持不变),否则它就会挂掉……
直线y=0是一堵墙,坐标(0,0)处开有一个洞,洞与蛇身的宽度都是一个可以忽略不计的小量。现在New Snake完全处于墙的上方(y>0),它想知道它自己的整个身体能否活着穿过墙洞,到达墙的下方(y<0)。
输入
每个测试点包含5组数据,以EOF结尾,对于每组数据:
第一行有1个整数N,表示New Snake折线顶点的个数。
接下来N行每行2个整数(xi, yi),描述这条折线。折线不会自交,折线上任意三个顶点都不共线。
输出
对于每组数据,输出Possible或Impossible,表示New Snake能否到达墙的下方。
样例输入
4
0 1
1 1
1 2
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
样例输出
Possible Impossible
提示
数据范围与约定
对于20%的数据,。
对于60%的数据,。
对于100%的数据,, , 折线不会自交,折线上任意三个顶点都不共线。