In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww’s speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane.
How long must he take to travel from A to D?
The first line is the case number T.
For each case, there are three lines.
The first line, four integers, the coordinates of A and B: Ax Ay Bx By.
The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy.
The third line, three integers, P Q R.
0<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10
The minimum time to travel from A to D, round to two decimals.
1
0 0 0 100
100 0 100 100
2 2 1
136.60
平面中两条线段 A B AB AB， C D CD CD，要求从 A A A 点走到 D D D 点，则先在 A B AB AB 上走一段，然后在两线段之间走一段，再上 C D CD CD 上走一段，三个地方的速度不同，求最短时间。
第一行是案例编号
T
T
T。
对于每种情况，有三行。
第一行，四个整数，
A
A
A 和
B
B
B 的坐标：
A
x
,
A
y
,
B
x
,
B
y
A_x,A_y,B_x,B_y
Ax?,Ay?,Bx?,By?。
第二行，四个整数，
C
C
C 和
D
D
D 的坐标：
C
x
,
C
y
,
D
x
D
y
C_x,C_y,D_x D_y
Cx?,Cy?,Dx?Dy?。
第三行，三个整数，
P
,
Q
,
R
P,Q,R
P,Q,R。
从 A A A 运动到 D D D 的最短时间，四舍五入到两位小数。
使用三分法。因为从一点到另一条直线上的点的距离的变化不是单调的，而是先减后增，所以需要三分中镶嵌三分。
先三分枚举
A
B
AB
AB 上的点
e
e
e，或者时间，对应于点
e
e
e 或者这个时间，去三分
C
D
CD
CD 段，找到对应
A
B
AB
AB 上当前点
e
e
e 对应的使整体花费时间最小的
B
C
BC
BC 上的点
f
f
f，然后在
A
B
AB
AB 上移动一下，
B
C
BC
BC 上搜一遍，继续移动，直到找到那个使整体花费时间最小的点，就是答案。
// C++ includes used for precompiling -*- C++ -*-
// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <Licenses - GNU Project - Free Software Foundation>.
/** @file stdc++.h
* This is an implementation file for a precompiled header.
*/
// 17.4.1.2 Headers
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define int long long
const double eps = 1e-9;//注意精度
struct project {
double x;
double y;
} a, b, c, d, e, f;
double p, q, r;
double disab, discd;
inline double dis(project A, project B) {
return sqrt(eps + (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
inline double calc(double t) {//t代表在f点在cd中位置的占比
f.x = d.x + (c.x - d.x) / discd * t * q;
f.y = d.y + (c.y - d.y) / discd * t * q;
return t + dis(e, f) / r;//在ef和fd上花费的时间
}
inline double findf(double t) {//找f
e.x = a.x + (b.x - a.x) / disab * t * p;
e.y = a.y + (b.y - a.y) / disab * t * p;//e点在线段AB中位置
double l = 0, r = discd / q, lmid, rmid;
while (l + eps < r) {
lmid = l + (r - l) / 3;
rmid = r - (r - l) / 3;
if (calc(lmid) < calc(rmid)) {
r = rmid;
} else {
l = lmid;
}
}
return t + calc(l);
}
inline int finde() {//找e
double l = 0.0, r = disab / p, lmid, rmid;
while (l + eps < r) {
lmid = l + (r - l) / 3;
rmid = r - (r - l) / 3;
if (findf(lmid) < findf(rmid)) {
r = rmid;
} else {
l = lmid;
}
}
return lmid;
}
inline void solve() {
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y >> p >> q >> r;
disab = dis(a, b);
discd = dis(c, d);
printf("%.2f\n", findf(finde()));
}
inline void work() {
int T;
cin >> T;
while (T--) {
solve();
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
work();
return 0;
}
你以为写完了？对，确实。