三分套三分 --- 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

 

 

 

目录
相关文章
PTA 7-2 找奇葩 (20 分)
在一个长度为 n 的正整数序列中,所有的奇数都出现了偶数次,只有一个奇葩奇数出现了奇数次。你的任务就是找出这个奇葩。
108 0
每日一题 --- 2055. 蜡烛之间的盘子[力扣][Go]
每日一题 --- 2055. 蜡烛之间的盘子[力扣][Go]
每日一题 --- 2055. 蜡烛之间的盘子[力扣][Go]
|
测试技术
PTA 1020 月饼 (25 分)
月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。
135 0
|
机器学习/深度学习 人工智能
PTA 7-3 拼题 A 是真爱 (20 分)
如果一个人在一段话里很多次提到 pintia,那对拼题 A 就是真爱啦~ 本题就请你检查一下给定的文字中出现了几次 pintia。
153 0
|
测试技术
PTA 7-1 祖传好运 (15 分)
我们首先定义 0 到 9 都是好运数,然后从某个好运数开始,持续在其右边添加数字,形成新的数字。
137 0
洛谷题库P1008---三连击
洛谷题库P1008---三连击
189 0
【CCCC】L2-029 特立独行的幸福 (25分),模拟题,set用法
【CCCC】L2-029 特立独行的幸福 (25分),模拟题,set用法
175 0