首页 > 代码库 > 二分三角形的时候尤其需要注意!!! HDU 5115 二分+模拟

二分三角形的时候尤其需要注意!!! HDU 5115 二分+模拟

 

题目大意:http://blog.csdn.net/snowy_smile/article/details/49535301

思路:分类讨论,分别在[1,2]、(2,3)、[3,4)、[4,1]相遇,然后再特判v1和v2的大小关系即可。

然后特别需要注意在(2,3)时候的二分了,因为我们二分非斜边的话,非斜边的增长速率大于斜边的增长速率

技术分享
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const double eps = 1e-6;const double len = 300.0;const double duijiao = sqrt(1.0*300*300*2);double t, v1, v2;int sign(double x){    return abs(x) < eps ? 0 : (x > 0 ? 1 : -1);}bool work_2_3(){    double t1, t2;    double lb = 0.0, rb = 300.0;    for (int i = 1; i <= 100; i++){        double mid = (lb + rb) / 2.0;        t1 = sqrt(1.0*300*300 + mid*mid) / v1;        t2 = (300.0 + mid) / v2;        ///if (sign(t1 - t2) > 0) rb = mid;        ///else lb = mid;        if (sign(t1 - t2) > 0) lb = mid;        else rb = mid;    }    t2 = (len - lb + len) / v2 + t;    t1 = (lb + len * 2.0) / v1;    if (sign(t1 - t2) > 0) return false;    return true;}bool work_3_4(){    double t1, t2;    double lb = 0.0, rb = 300.0;    for (int i = 1; i <= 100; i++){        double mid = (lb + rb) / 2.0;        t1 = (sqrt(1.0*300*300 + mid * mid)) / v1;        t2 = (len * 3.0 - mid) / v2;        if (sign(t1 - t2) > 0) rb = mid;        else lb = mid;    }    t2 = (len + lb) / v2 + t;    t1 = (sqrt(len*len + (len-lb)*(len-lb)) + 3*len) / v1;    if (sign(t1 - t2) > 0) return false;    return true;}bool solve(){    ///[1,2]    if (sign(v1 - v2) >= 0) return true;    if (v1 == 0) return false;    ///[1,4]    double t1 = len / v1, t2 = len * 3.0 / v2;    if (sign(t1 - t2) >= 0) return false;    t1 = duijiao / v1;    t2 = len * 2.0 / v2;    if (sign(t1 - t2) >= 0) return work_3_4();    else return work_2_3();}int main(){    int kase; cin >> kase;    for (int i = 1; i <= kase; i++) {        scanf("%lf%lf%lf", &t, &v1, &v2);        bool flag = solve();        if (flag) printf("Case #%d: Yes\n", i);        else printf("Case #%d: No\n", i);    }    return 0;}
View Code

 

二分三角形的时候尤其需要注意!!! HDU 5115 二分+模拟