【BZOJ1857】【SCOI2010】傳送帶 [三分]

傳送帶

Time Limit:?1 Sec??Memory Limit:?64 MB
[Submit][Status][Discuss]

Description

　　在一個2維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段AB和線段CD。lxhgww在AB上的移動速度為P，在CD上的移動速度為Q，在平面上的移動速度R。現在lxhgww想從A點走到D點，他想知道最少需要走多長時間

Input

　　輸入數據第一行是4個整數，表示A和B的坐標，分別為Ax，Ay，Bx，By 第二行是4個整數，表示C和D的坐標，分別為Cx，Cy，Dx，Dy 第三行是3個整數，分別是P，Q，R

Output

　　輸出數據為一行，表示lxhgww從A點走到D點的最短時間，保留到小數點后2位

Sample Input

　　0 0 0 100
　　100 0 100 100
　　2 2 1

Sample Output

　　136.60

HINT

　　對于100%的數據，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
　　1<=P，Q，R<=10

Main idea

　　給定平面上的兩條線段AB,CD，在AB,CD上移動會有一個特別的速度，在平面上移動會有一個速度，求從點A到點D的最短時間。

Solution

　　首先發現坐標范圍-1000~1000，并且精度要求不高，從此基礎上思考。我們先考慮從AB上一個定點O到CD上的距離，發現其中從O到CD的距離是先減小再增大的，我們大膽猜測這道題的答案滿足單峰性。然后我們可以用三分（效率為O(log1.5(n))）來實現。
　　我們現在可以求出一個定點求CD的最短時間，這里用三分實現。然后怎么辦呢？
　　由于AB也是一條線段，我們大膽猜測，可以再在AB上三分一個點，這樣就是三分套三分，最后發現其正確性可以證明。
　　三分方法（這里給出求最小值的方法）：在區間1/3處和2/3處各取兩個點l,r，如果左段（即L~l）的答案比右段（r~R）的更優，那么由于單峰性（圖像類似一個拋物線）可以抹去右段，多次操作使得答案最優。

Code

#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cmath>
#include<queue>
using namespace std;  
      
const int ONE=1005;
const int MOD=19650827;

int n;

struct power
{
        double x,y;
        double AB,CD,PM;
        friend power operator +(power a,power b) {a.x=a.x+b.x; a.y=a.y+b.y; return a;}
        friend power operator -(power a,power b) {a.x=a.x-b.x; a.y=a.y-b.y; return a;}
        
};
power A,B,C,D,v;
power l1,l2,r1,r2;
power a,b;
power pass;

int get()
{
        int res,Q=1;    char c;
        while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
        if(Q) res=c-48; 
        while((c=getchar())>=48 && c<=57) 
        res=res*10+c-48; 
        return res*Q; 
}

double dist(power a,power b)
{
        return (double)sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double Getdist(power E,power F)
{
        return dist(A,E)/v.AB + dist(E,F)/v.PM + dist(F,D)/v.CD;
}

double Trivide(power O)
{
        power l=C,r=D,pass,a,b;
        while(dist(l,r)>0.001)
        {
            pass.x=(r.x-l.x)/3.0;    pass.y=(r.y-l.y)/3.0;
            a=l+pass;    b=r-pass;
            if(Getdist(O,a) < Getdist(O,b)) r=b;
            else l=a;
        }
        return Getdist(O,l);
}

int main()
{
        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",&v.AB,&v.CD,&v.PM);    
        
        power l=A,r=B;
        while(dist(l,r)>0.001)
        {
            pass.x=(r.x-l.x)/3.0;    pass.y=(r.y-l.y)/3.0;
            a=l+pass;    b=r-pass;
            if(Trivide(a) < Trivide(b)) r=b;
            else l=a;
        }
        
        printf("%.2lf",Trivide(l));
}

?