Фигура из квадратов

////////////////////////////////////////////////////////////////////////////////////
//Даны действительные числа а1,в1,с1,а2,в2,с2,...аn, вn,cn. Эта последовательность 
//определяет на плоскости n квадратов со сторонами, параллельными осям: 
//аi, вi- координаты центра квадрата, сi-длина его стороны (i=1,...n).
//Определить площадь фигуры, образованной всеми квадратами.
////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <deque>
#include <iostream>
#include <functional>
#include <limits>
#include <numeric>
#include <set>
#include <vector>
////////////////////////////////////////////////////////////////////////////////////
typedef double  T_len;
////////////////////////////////////////////////////////////////////////////////////
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);
}
/////////////////////////////////////////////////////////////////////////////////////
template<class T>
struct T_less_for_real
{
    bool  operator() (T a, T b) 
    {
        return less_for_real(a, b); 
    }
};
/////////////////////////////////////////////////////////////////////////////////////
typedef  std::set<T_len, T_less_for_real<T_len> >  T_vertices_coord_set;
/////////////////////////////////////////////////////////////////////////////////////
class  T_square
{
    //------------------------------------------------------------------------------    
    T_len  c_X_;
    T_len  c_Y_;    
    T_len  a_;
    //------------------------------------------------------------------------------
public:
    T_square
        (
            T_len  c_X,
            T_len  c_Y,    
            T_len  a
        ) 
        : c_X_(c_X), c_Y_(c_Y), a_(a)
    {}
    //------------------------------------------------------------------------------
    T_len  X_min() const
    {
        return c_X_ - a_ / 2.0;  
    }
    //------------------------------------------------------------------------------
    T_len  X_max() const
    {
        return c_X_ + a_ / 2.0;  
    }
    //------------------------------------------------------------------------------
    T_len  Y_min() const
    {
        return c_Y_ - a_ / 2.0;  
    }
    //------------------------------------------------------------------------------
    T_len  Y_max() const
    {
        return c_Y_ + a_ / 2.0;  
    }
    //------------------------------------------------------------------------------   
};
////////////////////////////////////////////////////////////////////////////////////
typedef  std::vector<T_square>  T_squares;
////////////////////////////////////////////////////////////////////////////////////
T_len  get_area_total(const T_squares&  squares)
{    
    //Разграфим всю плоскость горизонтальными и вертикальными линиями, проходящими
    //через вершины заданных квадратов.
    T_vertices_coord_set  X_coord_set;
    T_vertices_coord_set  Y_coord_set;
 
    for(T_squares::const_iterator  square_it = squares.begin();
        square_it != squares.end(); ++square_it)
    {       
        X_coord_set.insert(square_it->X_min());
        X_coord_set.insert(square_it->X_max());
 
        Y_coord_set.insert(square_it->Y_min());
        Y_coord_set.insert(square_it->Y_max());        
    }    
 
    //Заполним векторы разностями соседних значений  множеств координат.
    typedef std::vector<T_len>  T_difference_coordinates;
 
    T_difference_coordinates  X_diff_coord;    
    std::adjacent_difference(X_coord_set.begin(), X_coord_set.end(), 
                             std::back_inserter(X_diff_coord));
 
    T_difference_coordinates  Y_diff_coord;
    std::adjacent_difference(Y_coord_set.begin(), Y_coord_set.end(), 
                             std::back_inserter(Y_diff_coord));
 
    //Удаляем в векторах первые элементы, так как разности начинаются со второго элемента.
    X_diff_coord.erase(X_diff_coord.begin());
    Y_diff_coord.erase(Y_diff_coord.begin());
 
    //Очевидно, что каждая клетка полученной решетки либо целиком принадлежит 
    //искомой фигуре, либо целиком не принадлежит. Для подсчета искомой площади
    //остается только пройтись по всем клеткам решетки и сложить площади клеток,
    //которые принадлежат хотя бы одному квадрату. Будем считать, что клетку 
    //описывает ее левая нижняя вершина. Заполняем решетку значениями false.
    typedef std::deque<bool>    T_row;
    typedef std::vector<T_row>  T_matr;        
    T_matr  matr(X_diff_coord.size(), T_row(Y_diff_coord.size()));
    
    T_len  area_total = 0;
    //Пробегаемся по всем квадратам:
    for(T_squares::const_iterator  square_it = squares.begin();
        square_it != squares.end(); ++square_it)
    {       
        //Обходим все клетки решетки, принадлежащие текущему квадрату, и, если 
        //в клетке false, вписываем туда true и прибавляем площадь клетки к общей сумме.
        int X_ind_begin 
            = std::distance(X_coord_set.begin(), X_coord_set.find(square_it->X_min()));
 
        int X_ind_end 
            = std::distance(X_coord_set.begin(), X_coord_set.find(square_it->X_max()));
 
        int Y_ind_begin 
            = std::distance(Y_coord_set.begin(), Y_coord_set.find(square_it->Y_min()));
 
        int Y_ind_end 
            = std::distance(Y_coord_set.begin(), Y_coord_set.find(square_it->Y_max()));
 
        for(int X_ind = X_ind_begin; X_ind != X_ind_end; ++X_ind)
        {
            for(int Y_ind = Y_ind_begin; Y_ind != Y_ind_end; ++Y_ind)
            {
                if(!matr[X_ind][Y_ind])
                {
                    matr[X_ind][Y_ind] = true;
                    area_total += X_diff_coord[X_ind] * Y_diff_coord[Y_ind];
                }
            }        
        }
    }
    return area_total;
}
////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
    int n = 0;
    do
    {
        std::cout << "Введите количество квадратов > 0: ";
        std::cin >> n;
    }while(n <= 0);    
 
    std::cout << "Введите параметры для "
              << n
              << " квадратов:"
              << std::endl;
    T_squares  squares;
    for(int i = 0; i < n; ++i)
    {
        std::cout << std::endl
                  << "Квадрат # "
                  << i + 1
                  << ":"
                  << std::endl
                  << '\t'
                  << "координаты центра: "
                  << std::endl
                  << '\t'
                  << '\t'
                  << " c_X = ";
        T_len c_X = 0;
        std::cin >> c_X;
        std::cout << '\t'
                  << '\t'
                  << " c_Y = ";
        T_len c_Y = 0;
        std::cin >> c_Y;
 
        std::cout << '\t'
            << "длина стороны: ";
        T_len a = 0;
        std::cin >> a; 
        squares.push_back(T_square(c_X, c_Y, a));
    }
    std::cout << "Площадь фигуры, образованной всеми квадратами равна: "
              << get_area_total(squares)
              << std::endl;
}