首页 > 代码库 > 二分三角形的时候尤其需要注意!!! 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;}
二分三角形的时候尤其需要注意!!! HDU 5115 二分+模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。