HDU 3400 Line belt 题解 三分镶嵌

发布时间:2024年01月18日

Line belt

传送门

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?

Input

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

Output

The minimum time to travel from A to D, round to two decimals.

Sample

Input

1
0 0 0 100
100 0 100 100
2 2 1

Output

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 上搜一遍,继续移动,直到找到那个使整体花费时间最小的点,就是答案。

AC Code

// 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;
}

你以为写完了?对,确实。

文章来源:https://blog.csdn.net/BestMonkey/article/details/135667122
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。