Решите задачу пожалуйста.

Координаты целочисленные или вещественные? Если целочисленные, то получаем поле из 4000000 миллионов клеток. И тупо считаем кол-во клеток, попадающих хотя бы в один прямоугольник.

Если же вещественные, то:

У нас есть 4 исходных прямоугольника - сумма их площадей S1, 6 прямоугольников, образованных попарным пересечением исходных - сумма их площадей S2, 3 прямоугольника, образованных пересечением трёх исходных - сумма их площадей S3, один прямоугольник, образованный пересечением всех четырёх прямоугольников - его площадь S4.

И, насколько понимаю, общая площадь: S = S1 - S2 + S3. У меня получилась такая формула, но я не уверен в её правильности.

Просто код, реализующий формулу включений-исключений.

 #include  

#include  

 

template 

struct Rectangle 

{ 

  T left, bottom, right, top; 

  Rectangle() : left(T(0)), bottom(T(0)), right(T(0)), top(T(0)) { } 

  Rectangle(const T x1, const T y1, const T x2, const T y2) : left(x1), bottom(y1), right(x2), top(y2) 

  {  

    if(left > right || bottom > top) left = right = bottom = top = T(0); 

  } 

}; 

 

template 

constexpr T Area(const Rectangle& rect) 

{ 

  return (rect.right - rect.left) * (rect.top - rect.bottom); 

} 

 

template 

constexpr Rectangle Intersection(const Rectangle& rect1, const Rectangle& rect2) 

{ 

  return Rectangle(std::max(rect1.left, rect2.left),  

                      std::max(rect1.bottom, rect2.bottom),  

                      std::min(rect1.right, rect2.right),  

                      std::min(rect1.top, rect2.top)); 

} 

 

int main()  

{ 

  const int n = 4; 

  Rectangle R[n]; 

  for(auto& r : R) std::cin >> r.left >> r.bottom >> r.right >> r.top; 

   

  int S = 0; 

  for(int i = 0; i < n; ++i) 

  { 

    S += Area(R[i]); 

    for(int j = i+1; j < n; ++j) 

    { 

      auto Rij = Intersection(R[i], R[j]); 

      S -= Area(Rij); 

      for(int k = j+1; k < n; ++k) 

      { 

        auto Rijk = Intersection(Rij, R[k]); 

        S += Area(Rijk); 

        for(int l = k+1; l < n; ++l) 

          S -= Area(Intersection(Rijk, R[l])); 

      } 

    } 

  } 

  std::cout

А простого алгоритма, наверное и нет. Решить "в лоб" можно так.
Пересечение двух прямоугольников - тоже прямоугольник.
Значит, нужна функция, которая вернёт пересечение двух прямоугольников (нужно придумать пустой прямоугольник; например, координаты (0,0,0,0) если пересечения нет).
Назовем пересечение вычетом.
.
Создаём список прямоугольников.
Записываем туда четыре прямоугольника, и запоминаем позицию в списке - 4.
По всем в списке от 0 до 3 находим площадь и суммируем.
Вложенным циклом находим все пересечения прямоугольников попарно, и записываем их в вершину списка (4..9).
Проходим от 4-ки вверх, находим площади и все их вычитаем.
Вложенным циклом проходим вверх уже от 4 до 9, находим пересечения вычетов попарно, но уже не записываем, а сразу находим их площади и прибавляем.
Всё.
Но есть ли тут ошибки, я не знаю.
Проще? Наверное можно, но не знаю, как.