Codeforces Round #327 (Div. 1) B. Chip 'n Dale Rescue Rangers 二分

題目連結：

題目

B. Chip 'n Dale Rescue Rangers

time limit per test：1 second

memory limit per test：256 megabytes

問題描述

A team of furry rescue rangers was sitting idle in their hollow tree when suddenly they received a signal of distress. In a few moments they were ready, and the dirigible of the rescue chipmunks hit the road.

We assume that the action takes place on a Cartesian plane. The headquarters of the rescuers is located at point (x1, y1), and the distress signal came from the point (x2, y2).

Due to Gadget's engineering talent, the rescuers' dirigible can instantly change its current velocity and direction of movement at any moment and as many times as needed. The only limitation is: the speed of the aircraft relative to the air can not exceed meters per second.

Of course, Gadget is a true rescuer and wants to reach the destination as soon as possible. The matter is complicated by the fact that the wind is blowing in the air and it affects the movement of the dirigible. According to the weather forecast, the wind will be defined by the vector (vx, vy) for the nearest t seconds, and then will change to (wx, wy). These vectors give both the direction and velocity of the wind. Formally, if a dirigible is located at the point (x, y), while its own velocity relative to the air is equal to zero and the wind (ux, uy) is blowing, then after seconds the new position of the dirigible will be .

Gadget is busy piloting the aircraft, so she asked Chip to calculate how long will it take them to reach the destination if they fly optimally. He coped with the task easily, but Dale is convinced that Chip has given the random value, aiming only not to lose the face in front of Gadget. Dale has asked you to find the right answer.

It is guaranteed that the speed of the wind at any moment of time is strictly less than the maximum possible speed of the airship relative to the air.

輸入

The first line of the input contains four integers x1, y1, x2, y2 (|x1|,  |y1|,  |x2|,  |y2| ≤ 10 000) — the coordinates of the rescuers' headquarters and the point, where signal of the distress came from, respectively.

The second line contains two integers and t (0 < v, t ≤ 1000), which are denoting the maximum speed of the chipmunk dirigible relative to the air and the moment of time when the wind changes according to the weather forecast, respectively.

Next follow one per line two pairs of integer (vx, vy) and (wx, wy), describing the wind for the first t seconds and the wind that will blow at all the remaining time, respectively. It is guaranteed that and .

輸出

Print a single real value — the minimum time the rescuers need to get to point (x2, y2). You answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

樣例

input

0 0 5 5

3 2

-1 -1

-1 0

output

3.729935587093555327

題意

救援飛船在(x1,y1)點，遇難者在(x2,y2)點，在前t秒時間裡刮一号風：(vx,vy)，在之後的時間裡刮二号風(wx,wy)，你飛船的最大速度為v，v大于風的速度。問你飛船能夠到達遇難者的最短的時間。

題解

首先，如果給我們的時間越多，我們就越能夠接近飛船！(一個特殊情況就是把飛船的前進方向控制在直線上。）也就是說，時間在可達和不可達的問題上是單調的！，我們可以對時間進行二分！求出最小的可行解！

那麼要怎麼判斷給定的時間t,飛船能不能到達遇難者的位置呢？

其實隻要給定固定的時間，我們的最優行路線是固定的！

速度是可以疊加的，我們可以考慮在t秒的時間，隻有風的作用下的情況，我們會從（x1,y1)到達（x1+tvx,y1+tvy)，記為(xm,ym)，接下來再考慮沒有風的情況下用速度v是否能從(xm,ym)到達(xt,yt)就可以了，即判斷v*t>=dis((xm,ym)->(xt,yt))是否成立;

那麼有兩段風怎麼辦？

我們可以考慮先判斷一下t秒這個時間是否可以到達，如果可以，那我們二分的範圍就是(0,t），且隻要考慮第一個風。 如果不可以，就二分（t,INF),且兩個風都要考慮（利用疊加的原理，其實和 上面一種情況沒什麼差。）。

代碼

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

typedef __int64 LL;
int xs,ys,xt,yt,v,t,vx,vy,wx,wy;
const int INF=0x3f3f3f3f;
const int TIM=1000;
const double eps=1e-8;

int Scan(){ int x; scanf("%d",&x); return x; }

void input(){
	xs=Scan(); ys=Scan();
	xt=Scan(); yt=Scan();
	v=Scan();  t=Scan();
	vx=Scan(); vy=Scan();
	wx=Scan(); wy=Scan();
}

int main(){
	input();
	double xm=xs+vx*t,ym=ys+vy*t;
	double dis=sqrt((xt-xm)*(xt-xm)+(yt-ym)*(yt-ym));
	if(1.0*v*t>=dis+eps){
		double l=0,r=t;
		while(r-l>eps){
			double mid=l+(r-l)/2;
			double _xm=xs+vx*mid,_ym=ys+vy*mid;
			double _dis=sqrt((xt-_xm)*(xt-_xm)+(yt-_ym)*(yt-_ym));
			if(1.0*v*mid>=_dis+eps) r=mid;
			else l=mid;
		} 
		printf("%.18lf\n",r);
	}else{
		double l=0,r=INF;
		while(r-l>eps){
			double mid=l+(r-l)/2;
			double _xm=xm+wx*mid,_ym=ym+wy*mid;
			double _dis=sqrt((xt-_xm)*(xt-_xm)+(yt-_ym)*(yt-_ym));
			if(1.0*v*(mid+t)>=_dis+eps) r=mid;
			else l=mid;
		}
		printf("%.18lf\n",r+t);
	}
	return 0;
}