Codeforces Round 365 (Div. 2)
C
Chris and Road
Codeforces
2100
原题
← BD →
翻译中…

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 $*n*$ vertices. 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* ≤ 10^{9}$, $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 $*x*_{*i*}$ and $*y*_{*i*}$ ($- 10^{9} ≤ *x*_{*i*} ≤ 10^{9}$, $0 ≤ *y*_{*i*} ≤ *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}$.

翻译中…

Note

翻译中…

Following image describes initial position in the first sample case:

翻译中…

image

翻译中…

样例

Input #1
5 5 1 2
1 2
3 1
4 3
3 4
1 4
Output #1
5.0000000000
InputCopy OutputCopy
题目信息
题号
703C
时间限制
2 s
内存限制
256 MB
标签
计算几何
模拟

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。