"целые" точки

//////////////////////////////////////////////////////////////////////////////////////
//На плоскости задан многоугольник (не обязательно выпуклый) координатами своих вершин.
//Нужно найти количество точек с целочисельными координатами, которые лежат 
//внутри многоугольника, не включая его сторон.
//Пример:
//4
//-1 -1
//-1 1
//1 1
//1 -1
//Ответ:
//1 
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <limits>
#include <set>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef double                  T_coord;
typedef std::complex<T_coord>   T_vertice;
typedef std::set<T_vertice>     T_vertices_set;
typedef std::vector<T_vertice>  T_polygon;
typedef std::vector<T_coord>    T_coords;
//////////////////////////////////////////////////////////////////////////////////////
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);
}
/////////////////////////////////////////////////////////////////////////////////////
bool  operator< (T_vertice  A, T_vertice  B)
{
    return  equal_to_for_real(A.real(), B.real()) 
                ? less_for_real(A.imag(), B.imag()) 
                : less_for_real(A.real(), B.real()) ;
}
/////////////////////////////////////////////////////////////////////////////////////
T_coord  det(T_vertice  A, T_vertice  B)
{
    return  A.real() * B.imag() - B.real() * A.imag();
}
/////////////////////////////////////////////////////////////////////////////////////
T_vertice  vect(T_vertice  A, T_vertice  B)
{
    return B - A;
}
/////////////////////////////////////////////////////////////////////////////////////
bool  lies_in_polygon
    (
        T_vertice         point,
        const T_polygon&  polygon
    )
{
    int  sides_intersections_counter = 0;
    for(size_t  i = 0; i < polygon.size(); ++i)
    {
        T_vertice       A = polygon[i];
        T_vertice       B = polygon[(i + 1) % polygon.size()];
        T_vertices_set  side_from_left_to_right;
        side_from_left_to_right.insert(A);
        side_from_left_to_right.insert(B);
        T_vertice  V_left   = *side_from_left_to_right.begin();
        T_vertice  V_right  = *side_from_left_to_right.rbegin();
 
        if(   point == V_left
           || point == V_right) return false; 
 
        T_coord    X_left   = V_left   .real();        
        T_coord    X_right  = V_right  .real();
 
        if(   equal_to_for_real  (X_left,         X_right        )
           && equal_to_for_real  (point.real(),   X_left         )
           && less_for_real      (V_left.imag(),  point.imag()   )
           && less_for_real      (point.imag(),   V_right.imag() )
          )
        {
            return  false;
        }
 
        bool     point_between_X  =    less_equal_for_real  (X_left,        point.real() )
                                    && less_for_real        (point.real(),  X_right      );
 
        T_coord  det_cur          = det(vect(V_left, V_right), vect(V_left, point));
 
        if(   point_between_X
           && equal_to_for_real(det_cur, 0.0))
        {
            return  false;
        }      
 
        if(   point_between_X
           && greater_for_real(det_cur, 0.0) )
        {
            ++sides_intersections_counter;
        }
    }
    return  sides_intersections_counter % 2 == 1;
}
/////////////////////////////////////////////////////////////////////////////////////
void  print_int_vertices_within_polygon
    (
        const T_polygon&      polygon,
        const T_vertices_set  vertices_set
    )
{
    int  point_counter = 0;
    //Получаем левую и правую проекции на ось X точек многоугольника.
    T_coord  X_min = vertices_set.begin()   ->real();
    T_coord  X_max = vertices_set.rbegin()  ->real();
 
    //Получаем нижнюю и верхнюю проекции на ось Y точек многоугольника.
    //Поворачиваем множество вершин по часовой стрелке на 90 градусов.
    T_vertices_set  turned_vertices_set;
    std::transform(vertices_set.begin(), vertices_set.end(), 
                   std::inserter(turned_vertices_set, turned_vertices_set.begin()),
                   std::bind2nd(std::multiplies<T_vertice>(), T_vertice(0.0, -1)));
 
    T_coord  Y_min = turned_vertices_set.begin()   ->real();
    T_coord  Y_max = turned_vertices_set.rbegin()  ->real();
 
    //Обходим целые клетки полученного прямоугольника и печатаем те, которые 
    //лежат внутри заданного многоугольника.
    int  X_int_min = static_cast<int>(floor  (X_min));
    int  X_int_max = static_cast<int>(ceil   (X_max));
 
    int  Y_int_min = static_cast<int>(floor  (Y_min));
    int  Y_int_max = static_cast<int>(ceil   (Y_max));
 
    std::cout << "Целые точки, лежащие внутри заданного многоугольника:"
              << std::endl;
    for(int X_int = X_int_min; X_int <= X_int_max; ++X_int)
    {
        for(int Y_int = Y_int_min; Y_int <= Y_int_max; ++Y_int)
        {
            T_vertice v(X_int, Y_int);
            if(lies_in_polygon(v, polygon))
            {
                ++point_counter;
                std::cout << v
                          << std::endl;
            }
        }
        std::cout << std::endl;
    }
    std::cout << "Всего "
              << point_counter
              << " точек."
              << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int  n = 0;
    do
    {
        std::cout << "Введите количество вершин многоугольника >= 1: ";
        std::cin >> n;
    }while(n < 1);
 
    std::cout << "Введите координаты "
              << n
              << " вершин многоугольника (можно невыпуклого):"
              << std::endl;
    T_vertices_set  vertices_set;
    T_polygon       polygon;
    do
    {
        std::cout << std::endl
                  << "X"
                  << vertices_set.size() + 1
                  << " = ";
 
        T_coord x = 0;
        std::cin >> x;
 
        std::cout << "Y"
                  << vertices_set.size() + 1
                  << " = ";
 
        T_coord y = 0;
        std::cin >> y;
 
        T_vertice  v(x, y);
        if(vertices_set.insert(v).second)
        {
            polygon.push_back(v);
        }
 
    }while(vertices_set.size() < static_cast<size_t>(n));
 
    print_int_vertices_within_polygon(polygon, vertices_set);    
}