XTU OJ 1175 Hurry Up(三分法&&穷举法）

Problem Description

GG is some what afraid of his MM. Once his MM asks, he will always try his best to rush to their home.
Obvious, he can run home in straight line directly. Alternatively, he can run to the main road and call the taxi.
You can assume there is only one main road on the x-axis, with unlimited length.
Given the initial location of GG and his destination, please help to ask the minimize time to get home.
GG will always run at the fixed speed of vr, and the taxi can move at the fixed speed of vt
You can also assume that, only GG reach the main road, he can catch the taxi immediately. And the taxi will go towards home ( not necessay along the road ).
Bisides, GG can run arbitrary length, and pay arbitrarily for the taxi.

P.S. MM: abbr. Ma Ma

Input

Multiple test cases. First line, an integer T ( 1 ≤ T ≤ 2000 ), indicating the number of test cases.
For each test cases, there are 6 integers x1, y1, x2, y2, vr, vt in a line.
( -1000 <= x1, y1, x2, y2 <= 1000, 1 <= vr < vt <= 1000 )
(x1, y1) : the initial location of GG
(x2, y2) : the destination location of GG
vr: GG‘s run speed
vt: taxi‘s speed

Ouput

For each test case, output a real number with 2 digits after the arithmetic point. It is the shorest time for GG to reach home.

Sample Input

2
1 1 2 2 1 2
1 1 2 2 1 7

Sample Output

1.41
1.32

Source

XTU OnlineJudge

这个题目昨天比赛的时候，想了好久，开始想的简单了，只能通过给的样例，提交上去wa了好几次，然后参看了一下别人的思路，说用穷举法，然后我们就自己写了一下，开始是以1为单位穷举，提交上去还是wa，后来我们用0.1为单位穷举，终于ac啦，但是我看了一下我们的用时，600多ms，后来，看别人是30多ms，问了一下，用的三分法。。。（感觉数据如果变态一点的话，穷举法可能就过不了了）朴素的算法做这些题还是不行啊，要学会优化！

三分法也是根据二分法来的，自己回来又写了一下三分法的，开始输入的时候用的c++的输入流，提交上去直接是100+ms了，后面全换成c语言的scanf，再提交40多ms了。

下面是三分法的代码：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#define E 1e-10 //这里是处理精度
using namespace std;
double x1,y11,x2,y22,vp,vt;//这里不能用y2，y2好像是c里面库函数的变量
double call(double x)
{
    return sqrt((x1-x)*(x1-x)+y11*y11)/vp+sqrt((x2-x)*(x2-x)+y22*y22)/vt;
}
double fun()
{
    double low,high,mid,mmid;
    if(x1>x2) swap(x1,x2);//交换
     low=x1,high=x2;
     while(low+E<high)
     {
         double v1,v2;
         mid=(low+high)/2;
         mmid=(mid+high)/2;
         v1=call(mid);
         v2=call(mmid);
         if(v1<=v2)
         {
             high=mmid;
         }
         else low=mid;
     }
     return call(low);
}
int main()
{
    int t;
    //cin>>t;
    scanf("%d",&t);
    while(t--)
    {
        //cin >> x1 >> y11 >> x2 >> y22 >> vp >> vt;  以后输入数据很多的话尽量用c语言输入，字符和字符串的话还是c++比较方便
        scanf("%lf %lf %lf %lf %lf %lf",&x1,&y11,&x2,&y22,&vp,&vt);
        double p_time,t_time;
        p_time=sqrt((x2-x1)*(x2-x1)+(y22-y11)*(y22-y11))/vp;
        t_time=fun();
        printf("%.2lf\n",p_time<t_time?p_time:t_time);
    }
    return 0;
}

下面是穷举法的代码：

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
int main()
{
    int times;
    int x1,y1,x2,y2,vp,vt;
    double min,person_time,taxi_time;
    //cin >> times;
    scanf("%d",×);
    while(times--)
    {
        //cin >> x1 >> y1 >> x2 >> y2 >> vp >> vt;
        scanf("%d %d %d %d %d %d",&x1,&y1,&x2,&y2,&vp,&vt);
        x1*=10,x2*=10,y2*=10,y1*=10,vp*=10,vt*=10;//这里是处理区间，0.1的都乘以10换成1方便计算
        person_time = (double)sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))/vp;
        min = 1000;
        if(x2>=x1)
            for(int i=x1; i<=x2; i++)
            {
                taxi_time = sqrt((i-x1)*(i-x1)+y1*y1)/vp+sqrt((x2-i)*(x2-i)+y2*y2)/vt;
                if(taxi_time<min)
                    min = taxi_time;
            }
        else
            for(int i=x2; i<=x1; i++)
            {
                taxi_time = sqrt((i-x2)*(i-x2)+y2*y2)/vt+sqrt((x1-i)*(x1-i)+y1*y1)/vp;
                if(taxi_time<min)
                    min = taxi_time;
            }
        printf("%.2f\n",person_time<min?person_time:min);
    }
    return 0;
}