当前位置: 代码迷 >> 综合 >> 二分 Codeforces591D Chip 'n Dale Rescue Rangers
  详细解决方案

二分 Codeforces591D Chip 'n Dale Rescue Rangers

热度:16   发布时间:2023-12-14 03:39:26.0

传送门:点击打开链接

题意:前t秒,风速的向量为(vx,vy),t秒后风速的向量变成(wx,wy),刚开始在(x1,y1),要去(x2,y2),飞机速度的最大大小是v,问到达目的地至少需要多长的时间

思路:二分时间,那么就能求出风速对飞机位移的影响,那么影响后,现在与目的地的距离求出来,让飞机直行看是否能在时间内到达,就算验证二分是否满足条件了,剩下的二分就行。

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;int main() {double x1, y1, x2, y2; //FIN;double v, t, vx, vy, wx, wy;while(~scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &v, &t, &vx, &vy, &wx, &wy)) {double l = 0, r = 1e9, m;for(int i = 1; i <= 100; i++) {m = (l + r) / 2;double x = x1 + vx * min(m, t) + wx * max(m - t, 0.0);double y = y1 + vy * min(m, t) + wy * max(m - t, 0.0);double dist = sqrt((x - x2) * (x - x2) + (y - y2) * (y - y2));if(dist <= v * m) r = m;else l = m;}printf("%.10lf\n", l);}return 0;
}