Площадь перекрытия двух кварталов

В городе на карте отмечают прямоугольные кварталы (границы идут строго по осям X и Y). Иногда два проекта кварталов накладываются друг на друга, и архитектору нужно знать площадь общей части.

Каждый квартал задан координатами двух противоположных углов. Углы могут быть перечислены в любом порядке.

Найдите площадь пересечения двух прямоугольников. Если общей части нет (или они только касаются границей/углом), площадь считается равной 0.

Важно: координаты могут быть до 10^9 по модулю, а площадь — до 10^18 (как на олимпиадах, это может не помещаться в 32-битный тип).

Формат ввода: Две строки. В первой строке: четыре целых числа x1 y1 x2 y2 — два противоположных угла первого прямоугольника. Во второй строке: четыре целых числа x3 y3 x4 y4 — два противоположных угла второго прямоугольника.

Формат вывода: Одно целое число — площадь пересечения.

Ограничения: -10^9 ≤ xi, yi ≤ 10^9.

Пример Ввод:

0 0 5 4
2 1 6 4

Вывод:

9

Ключевое наблюдение: у осевых прямоугольников общая часть тоже прямоугольник, а значит её площадь можно найти как width * height, где width — длина пересечения проекций на ось X, а height — на ось Y.

Почему это работает: прямоугольник задаётся независимыми границами по X и Y. Если проекции на X не пересекаются — общей площади нет, то же для Y.

План:

• Для каждого прямоугольника «нормализуйте» ввод: из двух углов получите границы left=min(x1,x2), right=max(x1,x2), bottom=min(y1,y2), top=max(y1,y2).
• Найдите пересечение по X: левый край общей части — max(left1, left2), правый — min(right1, right2). Тогда w = min(right1,right2) - max(left1,left2).
• Аналогично по Y: h = min(top1,top2) - max(bottom1,bottom2).
• Если w <= 0 или h <= 0, то прямоугольники не пересекаются по площади (включая касание ребром/углом) → ответ 0.
• Иначе ответ w * h.

Мини-сниппет формулы: w = min(r1, r2) - max(l1, l2) h = min(t1, t2) - max(b1, b2)

Сложность: O(1) по времени и памяти.

Частая ошибка: забыть про случай касания и проверять w < 0 вместо w <= 0 (тогда при нулевой ширине/высоте получится «площадь 0, но как будто пересечение есть»). Также не забывайте нормализовать углы — они могут идти в любом порядке.