2477: Taxi in Berland
Description
Polycarp came to the capital of Berland to attend a major conference. In order not to be late, he called a taxi and asked the driver to take him as quickly as possible from the railway station to the building, which will host the conference. It is about to start in a few minutes!
The capital of Berland is a rectangular field with the width of w and the length of l. From a plane, this field is viewed as a rectangle with leftmost bottom corner at the point (0, 0) and the rightmost top corner at the point (w,l). Roads in the capital of Berland are continuous vertical and horizontal segments which are parallel to the coordinate axes. There are w+1 vertical roads and l+1 horizontal roads. The coordinates of the ends of i-th vertical road (0≤i≤w) are in points (i,0) and (i,l). The coordinates of the ends of j-th horizontal road (0≤j≤l) are in points (0,j) and (w,j). Thus, each point within the rectangular field with integer coordinates is a crossroads.
The railway station is located at the point of the field (x1,y1) with integer coordinates and the taxi will take Polycarp from this point. The major conference will be held in a building that is at the point (x2,y2) with integer coordinates.
Cars in the capital of Berland can travel only by roads, that is, from every intersection the car can go either left or right or up or down to the nearby crossroads (cars cannot leave the field boundaries during driving).
The taxi, which arrived for Polycarp, can accelerate and slow down with the acceleration which does not exceed a by the absolute value and the maximum speed of the taxi is vmax. The taxi can turn (even rotate to reverse the direction) without reducing the speed.
The order is strictly preserved in the capital of Berland and there are n police cars with speed radar equipped at crossroads of the city. The maximum speed allowed in the capital of Berland is vp so if a policeman is at the crossroads then the taxi driver will not pass this crossroads with a speed greater than vp (a policeman located at crossroads (xi,yi) measures the speed of a car in the moment when the car passes this crossroads). The taxi driver agrees to drive with any speed in any other point of city because there is no risk to be arrested.
The taxi starts from the point (x1,y1) with zero speed. Polycarp is so afraid of being late, that he agreed to literally jump out of the taxi at the moment when it is at the point (x2,y2). Therefore, the taxi may arrive to the end point of the path with any speed not exceeding vmax.
It is guaranteed that no two policemen share the same position. There is no policeman at points (x1,y1) and (x2,y2). Points (x1,y1) and (x2,y2) are distinct.
You have to find the minimum time after which the taxi driver will be able to arrive the destination without passing a policeman with speed exceeding vp.
The first line of the input contains six numbers w,l,n,a,vmax,vp (1≤w,l≤100,0≤n≤100, 0.01≤a≤5.00,1≤vmax,vp≤100). All given numbers are integers, except the acceleration a, which is a float number and is given with exactly two digits after the decimal point.
The second line of the input contains four integers x1,y1,x2,y2 (0≤x1,x2≤w,0≤y1,y2≤l)− where (x1,y1) are the coordinates of the starting point (the railway station) and (x2,y2) are the coordinates of the end point (the building where the conference will take place).
The following n lines contains two integers xi,yi (0≤xi≤w,0≤yi≤l)− the coordinates of crossroads occupied by the police.
It is guaranteed that no two policemen share the same position. There is no policeman at points (x1,y1) and (x2,y2). Points (x1,y1) and (x2,y2) are distinct.
The output should contain the only float number− the minimum time required for the taxi driver to drop off Polycarp from the railway station to the building hosting the conference. Relative or absolute error of the answer should not exceed 10-6.
5 5 1 0.50 3 1
2 1 4 1
3 1
2.8284271247