5473 - Crossing the Desert
时间限制 : 1 秒
内存限制 : 256 MB
在这个问题中,你需要计算出你为了徒步穿越沙漠而需要购买的食物量。
在你的出发地你可以在商店里购买食物而且你可以收集到无限的免费的水。沙漠中间可能存在一些绿洲。在每个绿洲你同样可以收集无限的水和储存食物,但是你没法再绿洲购买新的食物,同样的你在出发地也可以储存食物。你会得到起点、所有绿洲和终点的二维坐标,这些地方都可以视为平面直角坐标系上的点,在坐标系上每走过一单位相当于实际走一英里。
你每走一英里,你就需要消耗一单位食物和一单位水。我们假设这消耗是持续进行的,即你走了x英里就消耗了x单位食物和水。你只有当食物和水足够时才能前进,而当你在绿洲休息时则不会消耗食物和水。当然你也有你可以携带的食物和水的上限,而这上限就是你能携带的食物和水的单位和的最大值,任何时候你都不能携带超过上限的食物和水。
你需要确定到达终点所需要购买的最少食物量,你不需要在到达终点时还有食物和水盈余。由于商店只能整单位售卖食物且只有一百万单位的存货,你的答案必须是大于0小于等于一百万的整数。
请注意样例!
输入
第一行包含两个整数n和tot,表示有意义的位置的坐标个数和能携带的单位数量上限。接下来n行每行两个整数x和y,其中第一个坐标表示起点,最后一个坐标表示终点,中间其他的坐标都是绿洲。你不必经过所有绿洲,也不必按特定的顺序经过绿洲。
输出
有解时,输出你需要的最小食物量,无解时,输出Impossible。具体格式见样例。
样例
输入
4 100 10 -20 -10 5 30 15 15 35
输出
136 units of food
输入
2 100 0 0 100 100
输出
Impossible
输入
2 100 0 0 0 1
输出
1 unit of food
提示
数据规模和约定
n<=20。
来源
蓝桥杯