题目描述

贝茜要通过一条宽度为 w 的无限长度的水平马路。

不妨假设马路在一个二维平面中，马路的一端为直线 y=0，另一端为直线 y=w。

马路中有一条垂直的人行横道，恰好是连接 (0,0) 和 (0,w) 的线段。

贝茜当前位于人行横道的一端 ---- (0,0) 位置处。

它要沿着人行横道到达马路对面的 (0,w) 位置处。

贝茜只能以不超过 u（单位长度/秒）的速度沿任意方向在人行横道上进行移动。

移动过程中贝茜可以随时改变自己的移动速度，甚至于停下。

马路中有一辆车正在以恒定速度 v（单位长度/秒）向 x 轴反方向（x 坐标递减的方向）移动。

该车可以视作一个 n 个顶点的凸多边形。

如果某一时刻，贝茜所在位置严格位于车凸多边形内（凸多边形的顶点和边不算内部），则意味着它被车撞了。

给定车当前的位置，请你计算贝茜在不被车撞的前提下，成功穿过马路到达点 (0,w) 所需要的最短时间（单位：秒）。

输入格式
第一行包含四个整数 n,w,v,u。

接下来 n 行，按照逆时针的顺序，每行输出一个凸多边形的顶点坐标 (xi,yi)。

保证输入凸多边形是非退化的。

输出格式
输出一个实数 t，表示最短时间。

输出结果与标准答案的绝对或相对误差不超过 10−6 即视为正确。

数据范围
前 3 个测试点满足 3≤n≤5。
所有测试点满足 3≤n≤10000，1≤w≤109，1≤v,u≤1000，−109≤xi≤109，0≤yi≤w。

样例

5 5 1 2
1 2
3 1
4 3
3 4
1 4

情况1

情况2

情况3

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int eps=1e-8;
double dcmp(double a,double b){
    if(abs(a-b)<eps) return 0;
    if(a>b) return 1;
    return -1;
}
int main(){
    int n,w,v,u;
    scanf("%d%d%d%d",&n,&w,&v,&u);
    double k=(double)u/v,b=0;
    bool all_right=true;
    bool all_left=true;
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(dcmp(y,k*x)>0) all_right=false;
        if(dcmp(y,k*x)<0) all_left=false;
        b=min(b,y-k*x);
    }
    if(all_right||all_left) 
        printf("%lf\n",(double)w/u);
    else printf("%lf\n",(w-b)/u);

}