Расстояние

/////////////////////////////////////////////////////////////////////////////////////
//На плоскости своими координатами задано N точек. Рассмотрим набор прямых, 
//проведенных через все различные пары точек. Необходимо определить 
//наибольшее возможное расстояние от любой заданной точки, до любой 
//прямой построенной по двум другим точкам.
/////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <set>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////
typedef double                 T_coord;
typedef std::complex<T_coord>  T_point;
typedef std::vector<T_point>   T_points;
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  equal_to_for_real(T a, T b) 
{
    const T  coef = 10;
    return abs(a - b) < std::numeric_limits<T>::epsilon() * coef;
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  greater_for_real(T a, T b) 
{
    return a > b
           && !equal_to_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  less_for_real(T a, T b) 
{
    return a < b
           && !equal_to_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  greater_equal_for_real(T a, T b) 
{
    return !less_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
bool  less_equal_for_real(T a, T b) 
{
    return !greater_for_real(a, b);
}
/////////////////////////////////////////////////////////////////////////////////////
struct  T_bottom_left_compare
{
    bool operator() (T_point A, T_point B)
    {
        return equal_to_for_real(A.imag(), B.imag()) 
            ? less_for_real(A.real(), B.real()) : less_for_real(A.imag(), B.imag());
    }
};
/////////////////////////////////////////////////////////////////////////////////////
struct  T_polar_corner_compare
{   
    bool  operator() (T_point A, T_point B)
    {
        return equal_to_for_real(arg(A), arg(B)) 
                   ? less_for_real(abs(A), abs(B)) 
                   : less_for_real(arg(A), arg(B));
    }
};
/////////////////////////////////////////////////////////////////////////////////////
T_point  vect(T_point  A, T_point  B)
{
    return B - A;
}
/////////////////////////////////////////////////////////////////////////////////////
T_coord  det(T_point A, T_point B)
{
    return  A.real() * B.imag() - A.imag() * B.real();
}
/////////////////////////////////////////////////////////////////////////////////////
T_points  get_convex_hull_points(const T_points&  points)
{
    //Ищем выпуклую оболочку методом Грэхема (время работы O(n*lg(n))).
    
    //Находим левую из самых нижних точек заданной совокупности.
    T_point  bottom_point_old 
        = *std::min_element(points.begin(), points.end(), T_bottom_left_compare());    
    
    //Вычитаем из всех точек вектора точку bottom_point_old (тогда стартовая точка
    //переместится в начало координат) и записываем эти точки в множество, 
    //отсортированное по полярному углу.
    typedef std::set<T_point, T_polar_corner_compare>  T_convex_hull_points;
    T_convex_hull_points  convex_hull_points;
    
    std::transform(points.begin(), points.end(), 
                   std::inserter(convex_hull_points, convex_hull_points.begin()), 
                   std::bind2nd(std::minus<T_point>(), bottom_point_old));
 
    T_point  bottom_point = T_point();
 
    //Помещаем в стек стартовую точку и первую точку множества, удаляя их из множества.    
    T_points  stack;
 
    T_point  cur_point = bottom_point;
    stack.push_back           (cur_point);
    convex_hull_points.erase  (cur_point);
 
    cur_point = *convex_hull_points.begin();
    stack.push_back           (cur_point);
    convex_hull_points.erase  (cur_point);
 
    //В цикле проверяем, какой поворот образуют точки предпоследняя в стеке,
    //последняя в стеке, и текущая. Если это не левый поворот, то выталкиваем
    //точку из стека (если она там не одна), и вставляем туда текущую. 
    //В конце в стеке останутся точки оболочки.
    for(T_convex_hull_points::const_iterator  point_it = convex_hull_points.begin();
        point_it != convex_hull_points.end(); )
    {
        int last_ind       = stack.size()  - 1;
        int prev_last_ind  = last_ind      - 1;
        T_point  v1 = vect(stack[prev_last_ind], stack[last_ind]);    
        T_point  v2 = vect(stack[last_ind], *point_it); 
 
        if(det(v1, v2) <= 0)
        {
            stack.pop_back();
            if(1 < stack.size())
            {
                continue;
            }            
        }
        stack.push_back(*point_it);
        ++point_it;
    }
    //Прибавляем к каждой точке stack точку bottom_point_old.
    std::transform(stack.begin(), stack.end(), stack.begin(),                   
                   std::bind2nd(std::plus<T_point>(), bottom_point_old));
 
    return  stack;  
}
/////////////////////////////////////////////////////////////////////////////////////
T_coord  get_max_dist_from_point_to_line
    (
        T_points&  points,
        T_point&   A,
        T_point&   B,
        T_point&   C
    )
{
    const T_points  convex_hull_points  = get_convex_hull_points(points);
    T_coord         H_max               = 0;
    //Очевидно, что если в заданном множестве точка A и прямая BC являются искомыми, 
    //то точка A принадлежит выпуклой оболочке множества, т.е. достаточно сравнивать 
    //расстояния от прямых, проходящих через пары точек множества, до точек выпуклой оболочки.
    //
    //Очевидно также, что среди пар точек множества может встретиться много таких, 
    //что прямые, проходящие через них, расположены к точкам выпуклой оболочки гораздо ближе,
    //чем прямые, проходящие через пары точек выпуклой оболочки, поэтому логично
    //точки выпуклой оболочки поставить в начало вектора.
    struct  T_is_convex_hull_point
    {
        const T_points&  convex_hull_;
        T_is_convex_hull_point(const T_points&  convex_hull) : convex_hull_(convex_hull)
        {}
        bool operator() (T_point  point)
        {
            return  std::find(convex_hull_.begin(), convex_hull_.end(), point) 
                        != convex_hull_.end();
        }
    };
    std::partition(points.begin(), points.end(), T_is_convex_hull_point(convex_hull_points));
    //Перебираем все точки выпуклой оболочки:
    for(T_points::const_iterator  it_A = points.begin();
        it_A != points.begin() + convex_hull_points.size(); ++it_A)
    {        
        T_coord  X_A = it_A->real();
        T_coord  Y_A = it_A->imag();
        //Перебираем все сочетания по две точки множества, исключая точку *it_A.
        for(T_points::const_iterator  it_B = points.begin();
            it_B != points.end(); ++it_B)
        {
            if(it_B == it_A) continue;
            T_coord  X_B = it_B->real();
            T_coord  Y_B = it_B->imag();
            T_point  vect_BA = vect(*it_B, *it_A);
            //Очевидно, что если в процессе вычисления расстояний какое-то расстояние H 
            //является на данный момент наибольшим, то достаточно для текущей точки A 
            //выпуклой оболочки вычислять расстояния только до прямых, проходящих 
            //через такие пары точек, что каждая из точек пары лежит от точки A дальше, чем H.
            //В данном случае для скорости сравниваем манхэттенское расстояние.
            if(less_equal_for_real(abs(X_B - X_A) + abs(Y_B - Y_A), H_max)) continue;           
 
            for(T_points::const_iterator  it_C = it_B + 1; it_C != points.end(); ++it_C)
            {
                if(it_C == it_A) continue;
                T_coord  X_C = it_C->real();
                T_coord  Y_C = it_C->imag();                
                if(less_equal_for_real(abs(X_C - X_A) + abs(Y_C - Y_A), H_max)) continue;
                
                //Находим расстояние от точки A до прямой BC:
                T_point  vect_BC = vect(*it_B, *it_C);
                T_coord  dist_A_BC = abs(det(vect_BA, vect_BC) / abs(vect_BC));
                if(dist_A_BC > H_max)
                {
                    H_max = dist_A_BC;
                    A = *it_A;
                    B = *it_B;
                    C = *it_C;
                }
            }        
        }
    }
    return  H_max;
}
/////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
 
    const int N_min = 3;
    const int N_max = 700;
    
    int n = 0;
    do
    {
        std::cout << "Число точек "
                  << N_min
                  << " <= n <= "
                  << N_max
                  << ": ";  
        std::cin >> n;
    }while(n < N_min 
           || N_max < n);
    
    T_points  points;
    std::cout << "Введите координаты "
              << n
              << " точек:"
              << std::endl;
 
    while(points.size() < static_cast<size_t>(n))
    {
        std::cout << std::endl
                  << "X"
                  << points.size() + 1
                  << " = ";
        T_coord  X = 0;
        std::cin >> X;
 
        std::cout << "Y"
                  << points.size() + 1
                  << " = ";
        T_coord  Y = 0;
        std::cin >> Y;
 
        T_point  point_cur = T_point(X, Y);
        if(   points.empty()
           || std::find(points.begin(), points.end(), point_cur) == points.end())
        {
            points.push_back(point_cur);    
        }
    }
    
    T_point  A;
    T_point  B;
    T_point  C;
    
    T_coord  dist_max = get_max_dist_from_point_to_line(points, A, B, C);
    std::cout << "В заданном множестве точек наибольшее расстояние от точки "
              << A 
              << " множества "
              << std::endl
              << "до прямой, проходящей через точки "
              << B 
              << " и "
              << C
              << " множества, равно "              
              << dist_max
              << std::endl;
}