首页 > 代码库 > HDU 3400 Line belt (三分再三分)
HDU 3400 Line belt (三分再三分)
HDU 3400 Line belt (三分再三分)
ACM
题目地址:
HDU 3400 Line belt
题意:
就是给你两条线段AB , CD ,一个人在AB以速度p跑,在CD上以q跑,在其他地方跑速度是r。问你从A到D最少的时间。
分析:
先三分AB上的点,再三分CD上的点即可。
证明:
设E在AB上,F在CD上。
令人在线段AB上花的时间为:f = AE / p
,人走完Z和Y所花的时间为:g = EF / r + FD / q
。
f函数是一个单调递增的函数,而g很明显是一个先递减后递增的函数。两个函数叠加,所得的函数应该也是一个先递减后递增的函数。故可用三分法解之。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * File: 3400.cpp * Create Date: 2014-09-18 09:44:01 * Descripton: triple */ #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const double EPS = 1e-8; struct Point { double x; double y; } a, b, c, d, e, f; int t; double p, q, r; double dis(Point p1, Point p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } double calc(double alpha) { f.x = c.x + (d.x - c.x) * alpha; f.y = c.y + (d.y - c.y) * alpha; return dis(f, d) / q + dis(e, f) / r; } double inter_tri(double alpha) { e.x = a.x + (b.x - a.x) * alpha; e.y = a.y + (b.y - a.y) * alpha; double l = 0.0, r = 1.0, mid, mmid, cost; while (r - l > EPS) { mid = (l + r) / 2; mmid = (mid + r) / 2; cost = calc(mid); if (cost <= calc(mmid)) r = mmid; else l = mid; } return dis(a, e) / p + cost; } double solve() { double l = 0.0, r = 1.0, mid, mmid, ret; while (r - l > EPS) { mid = (l + r) / 2; mmid = (mid + r) / 2; ret = inter_tri(mid); if (ret <= inter_tri(mmid)) r = mmid; else l = mid; } return ret; } int main() { ios_base::sync_with_stdio(0); cin >> t; while (t--) { cin >> a.x >> a.y >> b.x >> b.y; cin >> c.x >> c.y >> d.x >> d.y; cin >> p >> q >> r; printf("%.2f\n", solve()); } return 0; }
HDU 3400 Line belt (三分再三分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。