| |
|
问题描述:
由于成功的解决了"人流统计","Internet大串联"等问题,市长特别准许小明一个月的假期。
酷爱挑战极限的小明计划用这一个月的假期去横穿撒哈拉大沙漠!小明的出发位置是(x0,y0),目的地是(x1,y1)。
在出发地(x0,y0)小明可以购买任意多的食品,而在大沙漠中的某些地方,小明可以将身上的食品贮存起来(一处地方贮存的量是没有限制的),下次来的时候可以取出来继续食用。
由于小明身上可以携带食品的数量有上限(否则他就可以一次买足食品然后直接去目的地了^_^),因此,小明可能需要利用沙漠中的一些地方来贮存食品。
已知小明在沙漠中可以采取直线行走的路线,而他每走一公里就要消耗一个单位的食品(如果走了1.25公里,则消耗1.25单位的食品)。在当地向导的帮助下,小明事先知道了沙漠中有N-2个点可以用来贮存食品,并且记录下了这些点确切的坐标位置。
节俭的小明并不希望买过多的食品从而导致浪费,你能帮他计算出至少需要买多少单位的食品才能穿越沙漠呢?或者根本无法穿越沙漠?
输入文件:desert.in
输入文件的第一行有两个整数:N和M。N表示沙漠中点的数目,而M表示小明可携带食品的上限。(2 ≤ N ≤ 50,1 ≤ M ≤ 100000)。
以下N行,每行有两个实数,表示一个点的坐标。第一个坐标是(x0,y0)为出发点;第二个坐标是(x1,y1)为目的地。(-1000 ≤ x,
y ≤ 1000)。
输出文件:desert.out
输出文件有一行。如果小明能穿越沙漠,则输出一个整数,表示小明至少需要买多少单位的食品(如果是小数,则入到整数,例如答案为12.1,则输出13);否则输出Impossible。
样例输入:desert.in
4 51
10 -20
15 35
-10 5
30 15
样例输出:
desert.out
Impossible
|
|
|