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 timeonly 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.
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.
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.
5 5 1 2
1 2
3 1
4 3
3 4
1 4
5.0000000000
Following image describes initial position in the first sample case:
这题简直坑上天
一个多边形给出各个顶点一开始位置，从右往左以v速度扫过去，人站在(0,0)，现在要到(0,w)去，速度不能超过u，问最小时间
首先，换个参考系，假设多边形不动，人和终点同时获得一个向右的速度v
然后这样想：如果某一时刻让人的速度小于u，那么这个一定可以用一段全速加上一段停止来替换。因此考虑减速是没有意义的，那么人要么全速要么停止
如果全速，人在x方向上有个向右的速度v，在y方向有个向上的速度u，它的轨迹是一条斜率为k=u/v的直线
如果停止，相当于人在x轴上向右滑动
显然应该先停止再运动
那么轨迹应该是这样的
这图一画出来做法显然啊，先看看直接走能不能走，不能走的话因为多边形一定是经过直线y=u/v*x的，而且是连着的一大块，那么一定可以找到一条直线，使得这条直线恰好相切，而且右边的直线都相离。这显然可以二分
至于看看直线有没有穿过内部，看看点是不是都在直线一侧就好了。这里我直接判p[i].y-k*p[i].x-b大于还是小于0而懒得用向量做了
这题真的有毒啊。。eps设成1e-9就T了设成1e-7就A
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define eps 1e-7
using namespace std;
inline LL read()
{
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void write(LL a)
{
if (a<){printf("-");a=-a;}
if (a>=)write(a/);
putchar(a%+'');
}
inline void writeln(LL a){write(a);printf("\n");}
int n,w,v,u;
double l,r,k,b,ans;
struct point{int x,y;}p[];
inline bool jud(long double k,long double b)
{
int tota=,totb=;
for (int i=;i<=n;i++)
{
if (k*p[i].x+b-p[i].y<)tota++;
else totb++;
if (tota&&totb)return ;
}
return ;
}
int main()
{
n=read();w=read();v=read();u=read();
for (int i=;i<=n;i++)
{
p[i].x=read();
p[i].y=read();
}
k=(double)u/v;
if (jud(k,0.0)){printf("%.8lf",(double)w/u);return ;}
l=;r=1e9;
while (r-l>eps)
{
double mid=(l+r)/;
if (jud(k,(double)-mid/v*u)){ans=(double)w/u+mid/v;r=mid;}
else l=mid;
}
printf("%.8lf\n",ans);
}
cf703C