Задача о 9 точках

///////////////////////////////////////////////////////////////////////////////
//6.
///////////////////////////////////////////////////////////////////////////////
//Нужно сделать программу,которая сможет решить такую задачку.Даны(нарисованы)-
//9 точек по квадрату с одинаковым расстоянием друг от друга.Вот так:
//* * *
//* * *
//* * *
//Требуется:соединить их 4мя прямыми линиями - не отрывая карандаш от бумаги(ну если
//рисовать на бумаге)
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <set>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef int                             T_coord;
typedef std::complex    < T_coord   >   T_point;
typedef T_point                         T_shift;
///////////////////////////////////////////////////////////////////////////////
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 T_points                            T_segment;
typedef std::set        < T_segment     >   T_segments;
typedef std::vector     < T_segment     >   T_solution;
typedef std::set        < int           >   T_indexes_set;
///////////////////////////////////////////////////////////////////////////////
class   T_square
{
    //-------------------------------------------------------------------------
    static  const   int     SQUARE_DIM  =   3;
    //-------------------------------------------------------------------------
    T_points                points_;
    T_segments              segments_;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    T_square()
    {
        fill_points     ();
        fill_segments   ();
    }
    //-------------------------------------------------------------------------
    void    println_solutions()                                             const
    {
        int     ind{};
 
        for( auto   const   &   segment_1   :   segments_ )
        {
            for( auto   const   &   segment_2   :   segments_ )
            {
                for( auto   const   &   segment_3   :   segments_ )
                {
                    for( auto   const   &   segment_4   :   segments_ )
                    {
                        T_solution  solution    {
                                                    segment_1,
                                                    segment_2,
                                                    segment_3,
                                                    segment_4
                                                };
                        if  (
                                solution_is_valid( solution )
                            )
                        {
                            println_solution_with_ind
                                (
                                    solution,
                                    ++ind
                                );
                        }
                    }//for
                }//for
            }//for
        }//for
 
        std::cout   <<  (
                            ind
                                ?   "End."
                                :   "Solutions not found."
                        )
 
                    <<  std::endl;
    }
    //-------------------------------------------------------------------------
private:
    //-------------------------------------------------------------------------
    bool    solution_is_valid( T_solution   const   &   solution )          const
    {
        return
            adjacent_segments_are_not_parallel                          ( solution )
        &&  connection_points_of_segments_are_out_of_their              ( solution )
        &&  segments_are_connected_with_neighbors_of_different_ends     ( solution )
        &&  solution_contains_all_points                                ( solution );
    }
    //-------------------------------------------------------------------------
    bool    solution_contains_all_points( T_solution   const   &   solution )   const
    {
        T_points    res;
 
        for( auto   const   &   segment     :   solution )
        {
            res.insert
                (
                    segment.begin   (),
                    segment.end     ()
                );
        }
 
        return  res     ==  points_;
    }
    //-------------------------------------------------------------------------
    static
    bool    adjacent_segments_are_not_parallel( T_solution   const   &   solution )
    {
        for( size_t  i{}; i < solution.size() - 1; ++i )
        {
            if  (
                    segments_are_parallel
                        (
                            solution[i],
                            solution[i + 1]
                        )
                )
            {
                return  false;
            }
        }//for
 
        return  true;
    }
    //-------------------------------------------------------------------------
    static
    bool    segments_are_parallel
        (
            T_segment   const   &   segment_A,
            T_segment   const   &   segment_B
        )
    {
        return      standard_shift( segment_A )
                ==  standard_shift( segment_B );
    }
    //-------------------------------------------------------------------------
    static
    T_shift     standard_shift( T_segment   const   &   segment )
    {
        return  standard_shift
                    (
                        front   ( segment ),
                        back    ( segment )
                    );
    }
    //-------------------------------------------------------------------------
    static
    T_shift     standard_shift
        (
            T_point     const   &   A,
            T_point     const   &   B
        )
    {
        T_shift     shift   =   B   -   A;
 
        if  (
                    shift.real()    %   2   ==  0
                &&  shift.imag()    %   2   ==  0
            )
        {
            shift   /=  2;
        }
 
        if  (
                    shift.real()        <   0
 
                ||      shift.real()    ==  0
                    &&  shift.imag()    <   0
            )
        {
            shift   *=  -1;
        }
 
        return  shift;
    }
    //-------------------------------------------------------------------------
    static
    bool    connection_points_of_segments_are_out_of_their
        ( T_solution   const   &   solution )
    {
        for( size_t  i{}; i < solution.size() - 1; ++i )
        {
            if  (
                    !connection_point_of_segments_are_out_of_their
                        (
                            solution[i],
                            solution[i + 1]
                        )
                )
            {
                return  false;
            }
        }//for
 
        return  true;
    }
    //-------------------------------------------------------------------------
    static
    bool    connection_point_of_segments_are_out_of_their
        (
            T_segment   const   &   segment_1,
            T_segment   const   &   segment_2
        )
    {
        return      !segment_crosses_line_of_segment
                        (
                            segment_1,
                            segment_2
                        )
 
                &&  !segment_crosses_line_of_segment
                        (
                            segment_2,
                            segment_1
                        );
    }
    //-------------------------------------------------------------------------
    static
    bool    segment_crosses_line_of_segment
        (
            T_segment   const   &   segment_1,
            T_segment   const   &   segment_2
        )
    {
        return      distance_from_point_to_segment
                        (
                            front( segment_1 ),
                            segment_2
                        )
 
                *   distance_from_point_to_segment
                        (
                            back( segment_1 ),
                            segment_2
                        )
 
                <   0;
    }
    //-------------------------------------------------------------------------
    static
    double  distance_from_point_to_segment
        (
            T_point     const   &   point,
            T_segment   const   &   segment
        )
    {
        return  distance_from_point_to_line_of_points
                    (
                        point,
                        front   ( segment ),
                        back    ( segment )
                    );
    }
    //-------------------------------------------------------------------------
    static
    double  distance_from_point_to_line_of_points
        (
            T_point     const   &   point,
            T_point     const   &   _1,
            T_point     const   &   _2
        )
    {
        double  x   =   point.real();
        double  y   =   point.imag();
 
        double  x1  =   _1.real();
        double  y1  =   _1.imag();
 
        double  x2  =   _2.real();
        double  y2  =   _2.imag();
 
        return      ( y1    -   y2 )    *   x
                +   ( x2    -   x1 )    *   y
                +   x1                  *   y2
                -   x2                  *   y1;
    }
    //-------------------------------------------------------------------------
    template < typename     TT_set >
    static
    typename    TT_set::value_type  front( TT_set    const   &   set )
    {
        return  *set.begin();
    }
    //-------------------------------------------------------------------------
    template < typename     TT_set >
    static
    typename    TT_set::value_type  back( TT_set    const   &   set )
    {
        return  *set.rbegin();
    }
    //-------------------------------------------------------------------------
    static
    bool    segments_are_connected_with_neighbors_of_different_ends
        ( T_solution   const   &   solution )
    {
        for( size_t i{1}; i < solution.size() - 1; ++i )
        {
            if  (
                    !segment_directed_from_segment_to_segment_or_conversely
                        (
                            solution[i],
                            solution[i - 1],
                            solution[i + 1]
                        )
                )
            {
                return  false;
            }
        }//for
 
        return  true;
    }
    //-------------------------------------------------------------------------
    static
    bool    segment_directed_from_segment_to_segment_or_conversely
        (
            T_segment   const   &   segment,
            T_segment   const   &   segment_1,
            T_segment   const   &   segment_2
        )
    {
        return      segment_directed_from_segment_to_segment
                        (
                            segment,
                            segment_1,
                            segment_2
                        )
 
                ||  segment_directed_from_segment_to_segment
                        (
                            segment,
                            segment_2,
                            segment_1
                        );
    }
    //-------------------------------------------------------------------------
    static
    bool    segment_directed_from_segment_to_segment
        (
            T_segment   const   &   segment,
            T_segment   const   &   segment_1,
            T_segment   const   &   segment_2
        )
    {
        return      segment_directed_from_segment
                        (
                            segment,
                            segment_1
                        )
 
                &&  !segment_directed_from_segment
                        (
                            segment,
                            segment_2
                        );
    }
    //-------------------------------------------------------------------------
    static
    bool    segment_directed_from_segment
        (
            T_segment   const   &   segment,
            T_segment   const   &   seg_from
        )
    {
        return      fabs    (
                                distance_from_point_to_segment
                                    (
                                        front( segment ),
                                        seg_from
                                    )
                            )
 
                <   fabs    (
                                distance_from_point_to_segment
                                    (
                                        back( segment ),
                                        seg_from
                                    )
                            );
    }
    //-------------------------------------------------------------------------
    void    fill_points()
    {
        for( T_coord  i{}; i < SQUARE_DIM; ++i )
        {
            for( T_coord  j{}; j < SQUARE_DIM; ++j )
            {
                points_.insert( T_point(i, j) );
            }//for
        }//for
    }
    //-------------------------------------------------------------------------
    void    fill_segments()
    {
        for( auto   const   &   A   :   points_ )
        {
            for( auto   const   &   B   :   points_ )
            {
                if( A != B )
                {
                    segments_.insert
                        (
                            make_segment( A, B )
                        );
                }//if
            }//for
        }//for
    }
    //-------------------------------------------------------------------------

    T_segment   make_segment
        (
            T_point     const   &   A,
            T_point     const   &   B
        )                                                                   const
    {
        T_segment   res{A, B};
 
        for( auto   const   &   point   :   points_ )
        {
            if  (
                    res.count( point )
                )
            {
                continue;
            }
 
            if  (
                        standard_shift( A,  point   )
                    ==  standard_shift( A,  B       )
                )
            {
                res.insert( point );
            }
        }//for
 
        return  res;
    }
    //-------------------------------------------------------------------------
    static
    void    println_solution_with_ind
        (
            T_solution  const   &   solution,
            int                     ind
        )
    {
        std::cout   <<  "solution # "
                    <<  ind
                    <<  ":"
                    <<  std::endl;
 
        for( int  i{ SQUARE_DIM - 1 }; i >= 0; --i )
        {
            for( int  j{}; j < SQUARE_DIM; ++j )
            {
                print_segments_indexes_for_point_of_solution
                    (
                        T_point(i, j),
                        solution
                    );
 
                std::cout   <<  '\t';
            }//for j
 
            std::cout   <<  std::endl
                        <<  std::endl;
        }//for i
 
        std::cout   <<  std::endl
                    <<  std::endl;
    }
    //-------------------------------------------------------------------------
    static
    void    print_segments_indexes_for_point_of_solution
        (
            T_point     const   &   point,
            T_solution  const   &   solution
        )
    {
        T_indexes_set   segments_indexes;
 
        for( size_t  i{}; i < solution.size(); ++i )
        {
            if  (
                    solution[i].count( point )
                )
            {
                segments_indexes.insert(i);
            }
        }//for
 
        if  (
                segments_indexes.empty()
            )
        {
            std::cout   <<  "*";
        }
        else
        {
            for( auto   const   &   segm_index   :   segments_indexes )
            {
                if  (
                        segm_index  !=  front( segments_indexes )
                    )
                {
                    std::cout   <<  ",";
                }
 
                std::cout   <<  segm_index  +   1;
            }//for
        }//else
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::ios::sync_with_stdio( false );
    T_square  square;
    square.println_solutions();
}