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

В декартовой системе координат существует 4 прямоугольника, они могут пересекаться. На вход даётся 4 строчки с координатами x y левого нижнего и правого верхнего угла прямоугольников, все координаты по модулю не превосходят 1000. Нужно найти площадь, которую они занимают. Пересекающиеся области надо считать только один раз.
Пример :
Ввод :
3 1 6 3
1 2 4 7
2 4 6 8
5 2 7 6
Вывод :
35

Заранее спасибо! Пытался сам решить, но так и не придумал алгоритм.

По дате

По Рейтингу

andrei_6534

Новичок

1г

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

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

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

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

olga_semenova_4260

Гуру

1г

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

user_81327972

Мудрец

1г

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

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455

 #include <iostream> 
#include <algorithm> 
 
template<typename T> 
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<typename T> 
constexpr T Area(const Rectangle<T>& rect) 
{ 
  return (rect.right - rect.left) * (rect.top - rect.bottom); 
} 
 
template<typename T> 
constexpr Rectangle<T> Intersection(const Rectangle<T>& rect1, const Rectangle<T>& rect2) 
{ 
  return Rectangle<T>(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<int> 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 << S; 
  return 0; 
}