三分套三分 --- HDU 3400 Line belt

简介: Line belt Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=3400   Mean:  给出两条平行的线段AB, CD,然后一个人在线段AB的A点出发,走向D点,其中,人在线段AB上的速度为P, 在线段CD上的速度为Q,在其他地方的速度为R,求人从A点到D点的最短时间。

 Line belt

Problem's Link:   http://acm.hdu.edu.cn/showproblem.php?pid=3400


 

Mean: 

给出两条平行的线段AB, CD,然后一个人在线段AB的A点出发,走向D点,其中,人在线段AB上的速度为P, 在线段CD上的速度为Q,在其他地方的速度为R,求人从A点到D点的最短时间。

 

analyse:

经典的三分套三分。

首先在AB线段上三分,确定一个点,然后再在CD上三分,确定第二个点,计算出answer。也就是嵌套的三分搜索。

Time complexity: O(logn*logm)

 

Source code: 

//  Memory   Time
//  1347K     0MS
//   by : crazyacking
//   2015-03-31-23.22
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define MAXN 1000010
#define LL long long
using namespace std;
struct point
{
        double x,y;
};
point A,B,C,D;
double p,q,r;
double length(point X,point Y)
{
    return sqrt((X.x-Y.x)*(X.x-Y.x)+(X.y-Y.y)*(X.y-Y.y));
}
double time(double a,double b)
{
    point X,Y;
    X.x=a*(B.x-A.x)+A.x;
    X.y=a*(B.y-A.y)+A.y;
    Y.x=b*(C.x-D.x)+D.x;
    Y.y=b*(C.y-D.y)+D.y;
    return length(A,X)/p+length(D,Y)/q+length(X,Y)/r;
}
double ThiDiv(double alen)
{
        double l=0.0,r=1.0,lm,rm;
        while(r-l>1e-10)
        {
                lm=(l*2.0+r)/3;
                rm=(l+r*2.0)/3;
                if(time(alen,lm)>=time(alen,rm))
                        l=lm;
                else r=rm;
        }
        return time(alen,lm)<time(alen,rm)?time(alen,lm):(time(alen,rm));
}
int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(0);
//      freopen("C:\\Users\\Devin\\Desktop\\cin.cpp","r",stdin);
//      freopen("C:\\Users\\Devin\\Desktop\\cout.cpp","w",stdout);
        int Cas;
        scanf("%d",&Cas);
        while(Cas--)
        {
                scanf("%lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y);
                scanf("%lf %lf %lf %lf",&C.x,&C.y,&D.x,&D.y);
                scanf("%lf %lf %lf",&p,&q,&r);
                double l=0.0,r=1.0,lm,rm;
                while(r-l>1e-10)
                {
                        lm=(l*2.0+r)/3;
                        rm=(l+r*2.0)/3;
                        if(ThiDiv(lm)>=ThiDiv(rm))
                                l=lm;
                        else r=rm;
                }
                printf("%.2f\n",min(ThiDiv(lm),ThiDiv(rm)));
        }
        return 0;
}
/*

*/
View Code

 

 

 

目录
相关文章
|
6月前
【洛谷】P8707 [蓝桥杯 2020 省 AB1] 走方格
dp[1][j]=dp[i][1]=0 (因为每次只能向右或向下走,所以如果从(1,1)到第一行上所有的点的方案,只有水平向右走这一种。题目大意:现在有个人站在第 1 行第 1 列,要走到第 i 行第 j 列(每次只能向右或者向下走),如果行号和列号都是偶数,不能走入这一格中。因为不能走入行号和列号均为偶数的格子,所以当行号和列号均为偶数(也就是i%2==0&&j%2==0)时,dp[i][j]=0。因为我们已经考虑过了从(1,1)到第一行或者到第一列的情况,所以循环枚举时我们从(2,2)开始。
67 11
|
8月前
[蓝桥杯 2017 省 AB] 分巧克力
[蓝桥杯 2017 省 AB] 分巧克力
73 0
|
8月前
【每日一题Day298】LC13883n 块披萨 | 动态规划之打家劫舍
【每日一题Day298】LC13883n 块披萨 | 动态规划之打家劫舍
57 0
每日一题 --- 2055. 蜡烛之间的盘子[力扣][Go]
每日一题 --- 2055. 蜡烛之间的盘子[力扣][Go]
每日一题 --- 2055. 蜡烛之间的盘子[力扣][Go]
|
机器学习/深度学习 算法
【第十五届蓝桥杯备赛(bushi,写文凑个数)】蓝桥OJ---长草
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 BFS Flood Fill算法
190 0
|
机器学习/深度学习 人工智能
【第十五届蓝桥杯备赛(bushi,写文凑个数)】蓝桥OJ---排列序数
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 DFS
103 0
|
存储 人工智能 BI
P8597 [蓝桥杯 2013 省 B] 翻硬币个人思考总结+第五届传智杯ABC 初赛题解
桌上放着排成一排的若干硬币。我们用 `*` 表示正面,用 `o` 表示反面(是小写字母,不是零),比如可能情形是 `**oo***oooo`,如果同时翻转左边的两个硬币,则变为 `oooo***oooo`。现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
188 0
|
人工智能
凑算式---蓝桥杯
凑算式---蓝桥杯
凑算式---蓝桥杯
每日一题---蓝桥杯基础练习“01字串”
每日一题---蓝桥杯基础练习“01字串”