Вычислить момент времени когда расстояние между лидирующим и замыкающим велосипедистами будет минимальным

3            5
 
0 40       90 100
 
30 10      100 70
 
40 30      100 70
 
           110 60
 
           120 35
 
Вывод 1    Вывод 2
 
1 30          0.5 5.000000000000

3            5
 
0 40       90 100
 
30 10      100 70
 
40 30      100 70
 
           110 60
 
           120 35
 
Вывод 1    Вывод 2
 
1 30          0.5 5.000000000000

5
90 10
100 70
100 70
110 60
120 35

/////////////////////////////////////////////////////////////////////////////////////////
//Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который
//называется начальным, оказались в точках, удаленных от места старта на x1, x2, …, xn метров (n –
//общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной
//скоростью v1, v2, …, vn метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.
//Репортер, освещающий ход соревнований, хочет определить момент времени, в который
//расстояние между лидирующим в гонке велосипедистом и замыкающим гонку велосипедистом
//станет минимальным, чтобы с вертолета сфотографировать сразу всех участников велогонки.
//
//Требуется написать программу, которая по заданному количеству велосипедистов n, заданным
//начальным положениям велосипедистов x1, x2, …, xn и их скоростям v1, v2, …, vn, вычислит момент
//времени*t, в который расстояние l между лидирующим и замыкающим велосипедистом будет
//минимальным.
//
//ВВОД.
//Первая строка содержит целое число n – количество велосипедистов. В следующих n
//строках указаны по два целых числа: xi – расстояние от старта до i-го велосипедиста и vi – его
//скорость (0 ≤ xi, vi ≤ 107).
//
//ВЫВОД.
//В выходной файл необходимо вывести два вещественных числа: t – время в секундах,
//прошедшее от начального момента времени до момента, когда расстояние в метрах между
//лидером и замыкающим будет минимальным, l – искомое расстояние. Числа t и l должны иметь
//абсолютную или относительную погрешность не более 10-6, что означает следующее. Пусть
//выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным,
//если значение выражения |x – y| / max{1, |y|} не превышает 10-6.
//
//3            5
//
//0 40       90 100
//
//30 10      100 70
//
//40 30      100 70
//
//           110 60
//
//           120 35
//
//Вывод 1    Вывод 2
//
//1 30          0.5 5.000000000000
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <set>
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_cyclist
{
    int     x_;
    int     v_;
    //-----------------------------------------------------------------------------------
    double  get_x_for_time( double  time )                                          const
    {
        return  x_  +   v_  *   time;
    }
    //-----------------------------------------------------------------------------------
    bool    operator<   ( T_cyclist     const   &   cyclist )                       const
    {
        return      std::make_pair( x_,         v_          )
                <   std::make_pair( cyclist.x_, cyclist.v_  );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::set< T_cyclist     >   T_cyclists;
/////////////////////////////////////////////////////////////////////////////////////////
class   T_race
{
    //-----------------------------------------------------------------------------------
    T_cyclists  cyclists_;
    double      v_max_;
    double      precision_;
    double      group_len_min_;
    double      time_of_group_len_min_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_race  (
                T_cyclists  const   &   cyclists,
                double                  v_max,
                double                  precision
            )
        :
        cyclists_               ( cyclists      ),
        v_max_                  ( v_max         ),
        precision_              ( precision     ),
        group_len_min_          (),
        time_of_group_len_min_  ()
    {
        count_group_len_min_and_time();
    }
    //-----------------------------------------------------------------------------------
    double  time_of_group_len_min()                                                 const
    {
        return  time_of_group_len_min_;
    }
    //-----------------------------------------------------------------------------------
    double  group_len_min()                                                         const
    {
        return  group_len_min_;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    count_group_len_min_and_time()
    {
        double  time_L  =   0;
        double  time_R  =   1;
 
        while   (
                        group_len_for_time( time_L )
                    >   group_len_for_time( time_R )
                )
        {
            time_R  *=  2;
        }
 
        find_min_group_len_in_time_segment
            (
                time_L,
                time_R
            );
    }
    //-----------------------------------------------------------------------------------
    void    find_min_group_len_in_time_segment
        (
            double  time_L,
            double  time_R
        )
    {
        while   (
                    !precision_for_times_is_good
                        (
                            time_L,
                            time_R
                        )
                )
        {
            double  time_third  =   ( time_R    -   time_L ) / 3;
            double  time_L_new  =   time_L      +   time_third;
            double  time_R_new  =   time_R      -   time_third;
 
            if  (
                        group_len_for_time( time_L_new )
                    >   group_len_for_time( time_R_new )
                )
            {
                time_L  =   time_L_new;
            }
            else
            {
                time_R  =   time_R_new;
            }
        }//while
 
        time_of_group_len_min_  =   time_L;
        group_len_min_          =   group_len_for_time( time_L );
    }
    //-----------------------------------------------------------------------------------
    bool    precision_for_times_is_good
        (
            double  val_A,
            double  val_B
        )
    {
        double  val_min     =   val_A;
        double  val_max     =   val_B;
 
        if( val_min     >   val_max )
        {
            std::swap( val_min, val_max );
        }
 
        return                  ( val_max   -   val_min         )
                /   std::max    ( 1.0,          abs( val_min )  )   <=  precision_ / v_max_;
    }
    //-----------------------------------------------------------------------------------
    struct  T_count_min_and_max_x_for_time
    {
        //-------------------------------------------------------------------------------
        double  time_;
        double  x_min_;
        double  x_max_;
        bool    is_first_iteration_;
        //-------------------------------------------------------------------------------
        T_count_min_and_max_x_for_time( double  time )
            :
            time_                   ( time ),
            x_min_                  (),
            x_max_                  (),
            is_first_iteration_     ( true )
        {}
        //-------------------------------------------------------------------------------
        void    operator()  ( T_cyclist     const   &   cyclist )
        {
            auto    x_cur   =   cyclist.get_x_for_time( time_ );
 
            if( is_first_iteration_ )
            {
                x_min_  =   x_max_      =   x_cur;
                is_first_iteration_     =   false;
            }
            else
            {
                if( x_cur   <   x_min_ )
                {
                    x_min_  =   x_cur;
                }
 
                if( x_cur   >   x_max_ )
                {
                    x_max_  =   x_cur;
                }//if
            }
        }
        //-------------------------------------------------------------------------------
        operator    double()
        {
            return  x_max_ - x_min_;
        }
        //-------------------------------------------------------------------------------
    };
    //-----------------------------------------------------------------------------------
    double  group_len_for_time( double     time )                                   const
    {
        return  std::for_each
                    (
                        cyclists_.begin                 (),
                        cyclists_.end                   (),
                        T_count_min_and_max_x_for_time  ( time )
                    );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    std::cout   <<  "N = ";
    int     n   =   0;
    std::cin    >>  n;
 
    T_cyclists  cyclists;
    int         v_max   =   0;
 
    for( int  i = 0; i < n; ++i )
    {
        T_cyclist   cur_cyclist;
 
        std::cout   <<  std::endl
                    <<  "x"
                    <<  i + 1
                    <<  " = ";
 
        std::cin    >>  cur_cyclist.x_;
 
        std::cout   <<  "v"
                    <<  i + 1
                    <<  " = ";
 
        std::cin    >>  cur_cyclist.v_;
        v_max   =   std::max( v_max, cur_cyclist.v_ );
        cyclists.insert( cur_cyclist );
    }//for
 
    std::cout   <<  std::endl
                <<  "Допустимая погрешность вычислений: ";
    double  precision   =   0;
    std::cin    >>  precision;
 
    T_race  race    (
                        cyclists,
                        v_max,
                        precision
                    );
 
    std::cout   <<  std::endl
                <<  "time\t\t=\t"
                <<  race.time_of_group_len_min()
                <<  std::endl
                <<  "group_len_min\t=\t"
                <<  race.group_len_min()
                <<  std::endl;
 
    system("pause");
}

/////////////////////////////////////////////////////////////////////////////////////////
//Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который
//называется начальным, оказались в точках, удаленных от места старта на x1, x2, …, xn метров (n –
//общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной
//скоростью v1, v2, …, vn метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.
//Репортер, освещающий ход соревнований, хочет определить момент времени, в который
//расстояние между лидирующим в гонке велосипедистом и замыкающим гонку велосипедистом
//станет минимальным, чтобы с вертолета сфотографировать сразу всех участников велогонки.
//
//Требуется написать программу, которая по заданному количеству велосипедистов n, заданным
//начальным положениям велосипедистов x1, x2, …, xn и их скоростям v1, v2, …, vn, вычислит момент
//времени*t, в который расстояние l между лидирующим и замыкающим велосипедистом будет
//минимальным.
//
//ВВОД.
//Первая строка содержит целое число n – количество велосипедистов. В следующих n
//строках указаны по два целых числа: xi – расстояние от старта до i-го велосипедиста и vi – его
//скорость (0 ≤ xi, vi ≤ 107).
//
//ВЫВОД.
//В выходной файл необходимо вывести два вещественных числа: t – время в секундах,
//прошедшее от начального момента времени до момента, когда расстояние в метрах между
//лидером и замыкающим будет минимальным, l – искомое расстояние. Числа t и l должны иметь
//абсолютную или относительную погрешность не более 10-6, что означает следующее. Пусть
//выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным,
//если значение выражения |x – y| / max{1, |y|} не превышает 10-6.
//
//3            5
//
//0 40       90 100
//
//30 10      100 70
//
//40 30      100 70
//
//           110 60
//
//           120 35 
//
//Вывод 1    Вывод 2
//
//1 30          0.5 5.000000000000
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef double                          T_v;
typedef double                          T_x;
typedef std::set< T_x               >   T_x_values;
typedef std::map< T_v,  T_x_values  >   T_x_values_of_v;
/////////////////////////////////////////////////////////////////////////////////////////
class   T_race
{
    //-----------------------------------------------------------------------------------
    T_x_values_of_v     x_values_of_v_;
    double              precision_;
    double              group_len_min_;
    double              time_of_group_len_min_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_race  (
                T_x_values_of_v     const   &   x_values_of_v,
                double                          precision
            )
        :
        x_values_of_v_          ( x_values_of_v ),
        precision_              ( precision     ),
        group_len_min_          (),
        time_of_group_len_min_  ()
    {
        count_group_len_min_and_time();
    }
    //-----------------------------------------------------------------------------------
    double  time_of_group_len_min()                                                 const
    {
        return  time_of_group_len_min_;
    }
    //-----------------------------------------------------------------------------------
    double  group_len_min()                                                         const
    {
        return  group_len_min_;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    count_group_len_min_and_time()
    {
        double  time_L  =   0;
        double  time_R  =   1;
 
        while   (
                        group_len_for_time( time_L )
                    >   group_len_for_time( time_R )
                )
        {
            time_R  *=  2;
        }
 
        find_min_group_len_in_time_segment
            (
                time_L,
                time_R
            );
    }
    //-----------------------------------------------------------------------------------
    void    find_min_group_len_in_time_segment
        (
            double  time_L,
            double  time_R
        )
    {
        while   (
                    !precision_for_times_is_good
                        (
                            time_L,
                            time_R
                        )
                )
        {
            double  time_third  =   ( time_R    -   time_L ) / 3;
            double  time_L_new  =   time_L      +   time_third;
            double  time_R_new  =   time_R      -   time_third;
 
            if  (
                        group_len_for_time( time_L_new )
                    >   group_len_for_time( time_R_new )
                )
            {
                time_L  =   time_L_new;
            }
            else
            {
                time_R  =   time_R_new;
            }
        }//while
 
        time_of_group_len_min_  =   time_L;
        group_len_min_          =   group_len_for_time( time_L );
    }
    //-----------------------------------------------------------------------------------
    bool    precision_for_times_is_good
        (
            double  time_A,
            double  time_B
        )                                                                           const
    {
        double  time_min    =   time_A;
        double  time_max    =   time_B;
 
        if( time_min    >   time_max )
        {
            std::swap( time_min, time_max );
        }
 
        return                      ( time_max  -   time_min            )
                    /   std::max    ( 1.0,          abs( time_min )     )
 
                <=  precision_ / x_values_of_v_.rbegin()->first;
    }
    //-----------------------------------------------------------------------------------
    struct  T_count_min_and_max_x_for_time
    {
        //-------------------------------------------------------------------------------
        double  time_;
        double  x_min_;
        double  x_max_;
        //-------------------------------------------------------------------------------
        T_count_min_and_max_x_for_time( double  time )
            :
            time_                   ( time ),
            x_min_                  ( std::numeric_limits<double>::max()    ),
            x_max_                  ()
        {}
        //-------------------------------------------------------------------------------
        void    operator()  ( T_x_values_of_v::value_type  const   &   v_and_x_values )
        {
            auto    &   v           =   v_and_x_values.first;
            auto    &   x_values    =   v_and_x_values.second;
 
            std::for_each
                (
                    x_values.begin  (),
                    x_values.end    (),
 
                    [=]             ( double    x )
                    {
                        auto    x_cur   =   x + v * time_;
 
                        if( x_cur   <   x_min_ )
                        {
                            x_min_  =   x_cur;
                        }
 
                        if( x_cur   >   x_max_ )
                        {
                            x_max_  =   x_cur;
                        }//if
                    }//lambda
                );//for_each
        }
        //-------------------------------------------------------------------------------
        operator    double()                                                        const
        {
            return  x_max_ - x_min_;
        }
        //-------------------------------------------------------------------------------
    };
    //-----------------------------------------------------------------------------------
    double  group_len_for_time( double     time )                                   const
    {
        return  std::for_each
                    (
                        x_values_of_v_.begin            (),
                        x_values_of_v_.end              (),
                        T_count_min_and_max_x_for_time  ( time )
                    );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
void    input_val_with_ind_and_name
    (
        double          &   val,
        int                 ind,
        T_str   const   &   name
    )
{
    std::cout   <<  name
                <<  ind + 1
                <<  " = ";
 
    std::cin    >>  val;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    std::cout   <<  "N = ";
    int     n   =   0;
    std::cin    >>  n;
 
    T_x_values_of_v    x_values_of_v;
 
    for( int  i = 0; i < n; ++i )
    {
        std::cout   <<  std::endl;
 
        T_x     x   =   0;
        input_val_with_ind_and_name
            (
                x,
                i,
                "x"
            );
 
        T_v     v   =   0;
        input_val_with_ind_and_name
            (
                v,
                i,
                "v"
            );
 
        auto    &   x_values_cur   =   x_values_of_v[v];
 
        if  (
                x_values_cur.size()    >=  2
            )
        {
            if  (
                    x   <   *x_values_cur.begin()
                )
            {
                x_values_cur.erase( x_values_cur.begin() );
            }
 
            if  (
                    x   >   *x_values_cur.rbegin()
                )
            {
                x_values_cur.erase( --x_values_cur.end() );
            }
        }//if
 
        x_values_cur.insert(x);
    }//for
 
    std::cout   <<  std::endl
                <<  "Допустимая погрешность вычислений: ";
    double  precision   =   0;
    std::cin    >>  precision;
 
    T_race  race    (
                        x_values_of_v,
                        precision
                    );
 
    std::cout   <<  std::endl
                <<  "time\t\t=\t"
                <<  race.time_of_group_len_min()
                <<  std::endl
                <<  "group_len_min\t=\t"
                <<  race.group_len_min()
                <<  std::endl;
 
    system("pause");
}