题号:NC22575
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
Special Judge, 64bit IO Format: %lld
题目描述
众所周知,立体机动装置可以用腰部的发射机射出固定器,固定在巨人身上或是建筑物上后,再利用高压瓦斯将固定器的缆绳给卷回来使身体高速移动,并通过身体的摆动利用这立体的高速机动力来战斗。也就是说它可以让人在墙壁或大地的表面运动。
现在艾伦要使用立体机动装置从多边形城墙上一个顶点运动到墙角另一个顶点,求最短距离。
给出平面上一个n个点的凸多边形,表示城墙围城的区域。
将这个多边形当成一个直棱柱的底面。
给定直棱柱的高h(表示城墙的高度,城墙厚度忽略不计)、上表面上的一个顶点s和下表面上的一个顶点t。
问在不经过直棱柱上表面的情况下,沿直棱柱的表面从s走到t的最短距离。
输入描述:
第一行两个整数n(
),h(
)。
接下来n行,第i行两个实数
,
(
,不超过6位小数),表示第i个点的坐标。保证按逆时针顺序给出凸多边形上的点。
最后一行两个整数s,t(
),表示从上底面的第s个点到下底面的第t个点(按照输入顺序从1到n给点标号)。
输出描述:
一行一个实数,表示最小距离(绝对或相对误差不超过
即会被判为正确)。
示例2
说明
从上表面的(0, 1)从墙壁沿直线走到下表面的(2, 1),然后再由下表面的(2, 1)从下表面沿直线走到下表面的(3, 0)。