HDU 3400 Line belt

向右看齐 2022-05-14 05:11 142阅读 0赞

## 题目：[点击打开链接][Link 1] ##

## 题意：给定两条线段AB,CD，在这两条线段上速度分别为P，Q，在其他地方速度为R，让求A 到 D点的最短时间。 ##

## 分析：三分好题。 ##

## 如上图所示，红线部分为人走的路径。人所用的时间为 T = X / P + Y / Q + Z / R。   ![ds][]      然后我们做一个变形，令人在线段AB上花的时间为：F(X) = X / P ，假设X是一个确定值的前提下，   人走完Z和Y所花的时间为：   G(Y) = Z / R + Y / Q。当X 和Y都确定的情况下，Z也是一个确定值。所以，所求的函数可以写成：    T（X，Y) = F(X) + G(Y)。因为T是一个关于X和Y的函数，而G只是一个关于Y的函数，    所以，可以用两层嵌套的三分法解这个方程。首先以X为变量，对T进行三分。    在求G的值的时候，以Y为变量，对G进行三分，求出G在对应的X下的最小值。这样就能求出T的最小值了。     ##

## 两个函数叠加，所得的T（X,Y）函数应该也是一个先递减后递增的函数。故可用三分法解之。 ##

## 代码： ##

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-6
    #define PI acos(-1.0)
    typedef pair<int,int> PII;
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int t,p,q,rr;
    struct pt {
        double x,y;
    }a,b,c,d;
    
    double dis(pt a,pt b) {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    
    double ts(pt pp) {
        double ans=0;
        pt m,mm,l,r;
        l=c,r=d;
        while(1) {///保证一定进入循环，防止两点重合跳过循环体
            m.x=(l.x+r.x)/2,m.y=(l.y+r.y)/2;
            mm.x=(m.x+r.x)/2,mm.y=(m.y+r.y)/2;
            if(dis(pp,mm)/rr+dis(mm,d)/q <= dis(pp,m)/rr+dis(m,d)/q) ans=dis(pp,mm)/rr+dis(mm,d)/q,l=m;
            else ans=dis(pp,m)/rr+dis(m,d)/q,r=mm;
            if(dis(l,r)<eps) break;
        }
        return ans;
    }
    
    void sv() {
        double ans=0;
        pt m,mm,l,r;
        l=a,r=b;
        while(1) {///保证一定进入循环，防止两点重合跳过循环体
            m.x=(l.x+r.x)/2,m.y=(l.y+r.y)/2;
            mm.x=(m.x+l.x)/2,mm.y=(m.y+l.y)/2;
            if(dis(a,mm)/p+ts(mm) <= dis(a,m)/p+ts(m)) ans=dis(a,mm)/p+ts(mm),r=m;
            else ans=dis(a,m)/p+ts(m),l=mm;
            if(dis(l,r)<eps) break;
        }
        cout<<fixed<<setprecision(2)<<ans<<endl;
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>t;
        while(t--) {///整型当浮点数输入没有问题
            cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y>>p>>q>>rr;
            sv();
        }
        return 0;
    }

## 参考博客：[https://blog.csdn.net/became\_a\_wolf/article/details/51284492][https_blog.csdn.net_became_a_wolf_article_details_51284492] ##

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3400
[ds]: /images/20220514/5ef98c67b61d4474adce06e486e2b3d7.png
[https_blog.csdn.net_became_a_wolf_article_details_51284492]: https://blog.csdn.net/became_a_wolf/article/details/51284492