Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри - C++ - Ответ 9931388

///////////////////////////////////////////////////////////////////////////////
//2.
///////////////////////////////////////////////////////////////////////////////
//Даны N точек на плоскости. Найти среди них точки
//являющиеся вершинами фигуры, содержащей максимальное
//число заданных точек. Фигура - параллелограмм.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
#include <iterator>
#include <numeric>
#include <set>
#include <utility>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef double                          T_coord;
typedef std::complex    < T_coord   >   T_point;
typedef std::vector     < T_point   >   T_points_arr;
///////////////////////////////////////////////////////////////////////////////
namespace std
{
    bool    operator<
        (
            T_point     const   &   L,
            T_point     const   &   R
        )
    {
        return      std::make_pair(     L.real(),   L.imag()    )
                <   std::make_pair(     R.real(),   R.imag()    );
    }
}
///////////////////////////////////////////////////////////////////////////////
typedef std::set    < T_point   >   T_points;
typedef std::set    < T_points  >   T_parallelograms;
///////////////////////////////////////////////////////////////////////////////
T_coord     pseudoscalar
    (
        T_point     const   &   L,
        T_point     const   &   R
    )
{
    return      L.real  ()  *   R.imag  ()
            -   L.imag  ()  *   R.real  ();
}
///////////////////////////////////////////////////////////////////////////////
bool    triad_is_collinear( T_points_arr    const   &   triad )
{
    auto    A   =   triad[0];
    auto    B   =   triad[1];
    auto    C   =   triad[2];
 
    return      pseudoscalar
                    (
                        B   -   A,
                        C   -   A
                    )
 
            ==  0;
}
///////////////////////////////////////////////////////////////////////////////
void    add_parallelograms_of_triad
    (
        T_points            const   &   points,
        T_points_arr                    triad,
        T_parallelograms            &   parallelograms
    )
{
    if  (
            triad_is_collinear( triad )
        )
    {
        return;
    }
 
    for( size_t  i{}; i < triad.size(); ++i )
    {
        auto    A   =   triad[0];
        auto    B   =   triad[1];
        auto    C   =   triad[2];
 
        auto    D   =   -A + B + C;
 
        if  (
                points.count( D )
            )
        {
            parallelograms.insert   (
                                        {A, B, C, D}
                                    );
        }
 
        std::rotate
            (
                triad.begin     (),
                triad.begin     ()  +   1,
                triad.end       ()
            );
    }//for
}
///////////////////////////////////////////////////////////////////////////////
void    set_parallelograms_for_points
    (
        T_points    const   &   points,
        T_parallelograms    &   parallelograms
    )
{
    for (
            auto
            it_1  =   points.begin    ();
            it_1  !=  points.end      ();
            ++it_1
        )
    {
        for (
                auto
                it_2    =   std::next   ( it_1 );
                it_2    !=  points.end  ();
                ++it_2
            )
        {
            for (
                    auto
                    it_3    =   std::next   ( it_2 );
                    it_3    !=  points.end  ();
                    ++it_3
                )
            {
                add_parallelograms_of_triad
                    (
                        points,
                        {   *it_1,  *it_2,  *it_3   },
                        parallelograms
                    );
            }//for
        }//for
    }//for
}
///////////////////////////////////////////////////////////////////////////////
struct  T_point_is_inside_of_par
{
    //-------------------------------------------------------------------------
    T_points_arr    par_arr_;
    T_point         center_;
    //-------------------------------------------------------------------------
    T_point_is_inside_of_par( T_points     const   &   par )
        :
        par_arr_    (
                        par.begin   (),
                        par.end     ()
                    )
    {
        center_     =       std::accumulate
                                (
                                    par_arr_.begin  (),
                                    par_arr_.end    (),
                                    T_point         ()
                                )
 
                        /   T_point(    par_arr_.size()  );
 
        std::sort
            (
                par_arr_.begin   (),
                par_arr_.end     (),
 
                [&]             (
                                    auto  const   &   L,
                                    auto  const   &   R
                                )
                {
                    return      std::arg( L     -   center_ )
                            <   std::arg( R     -   center_ );
                }
            );
    }
    //-------------------------------------------------------------------------
    bool    operator()  ( T_point   const   &   p )
    {
        bool    bool_res{};
 
        for( size_t  i{}; i < par_arr_.size(); ++i )
        {
            bool_res    =   points_lie_on_one_side_of_segment
                                (
                                    p,
                                    center_,
 
                                    par_arr_[0],
                                    par_arr_[1]
                                );
 
            if( !bool_res )
            {
                break;
            }
 
            std::rotate
                (
                    par_arr_.begin  (),
                    par_arr_.begin  ()  +   1,
                    par_arr_.end    ()
                );
        }//for
 
        return  bool_res;
    }
    //-------------------------------------------------------------------------
    static
    bool    points_lie_on_one_side_of_segment
        (
            T_point     const   &   L,
            T_point     const   &   R,
 
            T_point     const   &   segm_v_1,
            T_point     const   &   segm_v_2
        )
    {
        return          pseudoscalar
                            (
                                L           -   segm_v_1,
                                segm_v_2    -   segm_v_1
                            )
 
                    *   pseudoscalar
                            (
                                R           -   segm_v_1,
                                segm_v_2    -   segm_v_1
                            )
 
                >=  0;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
struct  T_points_count_of_par
{
    //-------------------------------------------------------------------------
    T_points    const   &   points_;
    //-------------------------------------------------------------------------
    T_points_count_of_par( T_points     const   &   points  )
        :
        points_( points )
    {}
    //-------------------------------------------------------------------------
    int     operator()  ( T_points  const   &   par )                       const
    {
        return  std::count_if
                    (
                        points_.begin               (),
                        points_.end                 (),
                        T_point_is_inside_of_par    ( par )
                    );
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
void    set_parallelogram_containing_max_number_of_points
    (
        T_points    const   &   points,
        T_points            &   res_parallelogram
    )
{
    T_parallelograms    parallelograms;
 
    set_parallelograms_for_points
        (
            points,
            parallelograms
        );
 
    T_points_count_of_par  points_count_of_par( points );
 
    auto    it  =   std::max_element
                        (
                            parallelograms.begin    (),
                            parallelograms.end      (),
 
                            [&]                     (
                                                        auto  const   &   L,
                                                        auto  const   &   R
                                                    )
                            {
                                return      points_count_of_par(L)
                                        <   points_count_of_par(R);
                            }
                        );
 
    if  (
                it
            !=  parallelograms.end()
        )
    {
        res_parallelogram   =   *it;
    }
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    size_t  n{};
    std::cout   <<  "points total: ";
    std::cin    >>  n;
 
    std::cout   <<  "Input "
                <<  n
                <<  " points in form (1,2):"
                <<  std::endl;
 
    T_points    points;
 
    while   (
                    points.size()
                <   n
            )
    {
        T_point     point_cur;
 
        do
        {
            std::cout   <<  "point_"
                        <<  points.size() + 1
                        <<  "\t: ";
 
            std::cin    >>  point_cur;
        }
        while   (
                        !points.empty   ()
                    &&  points.count    ( point_cur )
                );
 
        points.emplace( point_cur );
    }//while
 
    T_points    res_parallelogram;
 
    set_parallelogram_containing_max_number_of_points
        (
            points,
            res_parallelogram
        );
 
    if  (
            res_parallelogram.empty()
        )
    {
        std::cout   <<  "no solution"
                    <<  std::endl;
    }
    else
    {
        std::cout   <<  "resulting parallelogram:"
                    <<  std::endl;
        for( auto   const   &   point   :   res_parallelogram )
        {
            std::cout   <<  point
                        <<  '\t';
        }//for
 
        std::cout   <<  std::endl;
    }//else
}