【CodeForces】703C - Chris and Road（思维，好题）

点击打开题目

C. Chris and Road

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

And while Mishka is enjoying her trip...

Chris is a little brown bear. No one knows, where and when he met Mishka, but for a long time they are together (excluding her current trip). However, best friends are important too. John is Chris' best friend.

Once walking with his friend, John gave Chris the following problem:

At the infinite horizontal road of width w, bounded by lines y = 0 and y = w, there is a bus moving, presented as a convex polygon of nvertices. The bus moves continuously with a constant speed of v in a straight Ox line in direction of decreasing x coordinates, thus in time only x coordinates of its points are changing. Formally, after time t each of x coordinates of its points will be decreased by vt.

There is a pedestrian in the point (0, 0), who can move only by a vertical pedestrian crossing, presented as a segment connecting points(0, 0) and (0, w) with any speed not exceeding u. Thus the pedestrian can move only in a straight line Oy in any direction with any speed not exceeding u and not leaving the road borders. The pedestrian can instantly change his speed, thus, for example, he can stop instantly.

Please look at the sample note picture for better understanding.

We consider the pedestrian is hit by the bus, if at any moment the point he is located in lies strictly inside the bus polygon (this means that if the point lies on the polygon vertex or on its edge, the pedestrian is not hit by the bus).

You are given the bus position at the moment 0. Please help Chris determine minimum amount of time the pedestrian needs to cross the road and reach the point (0, w) and not to be hit by the bus.

Input

The first line of the input contains four integers n, w, v, u (3 ≤ n ≤ 10 000, 1 ≤ w ≤ 109, 1 ≤ v,  u ≤ 1000) — the number of the bus polygon vertices, road width, bus speed and pedestrian speed respectively.

The next n lines describes polygon vertices in counter-clockwise order. i-th of them contains pair of integers xi and yi ( - 109 ≤ xi ≤ 109,0 ≤ yi ≤ w) — coordinates of i-th polygon point. It is guaranteed that the polygon is non-degenerate.

Output

Print the single real t — the time the pedestrian needs to croos the road and not to be hit by the bus. The answer is considered correct if its relative or absolute error doesn't exceed 10 - 6.

Example

input

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

output

5.0000000000

Note

Following image describes initial position in the first sample case:

看了学姐的题解，半天才想通。

分三种情况：

①人的速度很快，车没来人就过去了。

②车的速度很快，人买来车就过去了。

③人要调整速度以免相撞。

前两种都可以用最大速度过去，第三种需要调整。

这里只说第三种，人要想最快过去，那就等车子能碰到他的位置过去后再全速过去。这里我一直在纠结的问题是：如果把这个部位等过去了，那么会不会有其他的部位继续挡他一下？后来想通了，并不会，因为如果后面的会挡，我们就按照后面的数去更新结果了。还是多想想吧，我还是有点晕晕的，写完吃饭去~

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
int main()
{
	int n;
	double x,y,w,vb,vp;
	while (~scanf ("%d %lf %lf %lf",&n,&w,&vb,&vp))
	{
		int flag1 = 1;		//人是否能在汽车来之前通过
		int flag2 = 1; 		//人是否能在汽车通过前到达汽车边界
		double ans = 0;
		while (n--)
		{
			scanf ("%lf %lf",&x,&y);
			if (x/vb > y/vp)
				flag2 = 0;
			if (x/vb < y/vp)
				flag1 = 0;
			ans = max (ans , x/vb + (w-y)/vp);
		}
		if (flag1 + flag2 > 0)		//有一个成立就按最大速度走
			printf ("%.8lf\n",w/vp);
		else
			printf ("%.8lf\n",ans);
	}
	return 0;
}