У Вики есть бесконечный лист клетчатой бумаги. Изначально каждая клетка белого цвета. Она ввела на этом листе двумерную систему координат и нарисовала n чёрных горизонтальных и вертикальных отрезков, параллельных осям координат и шириной в одну клетку. Таким образом, каждый отрезок является множеством соседних клеток, расположенных в одной строке или в одном столбце.
Перед вами стоит задача посчитать число закрашенных клеток. Если клетка была покрашена более одного раза, в ответе она должна быть посчитана ровно один раз.
В первой строке входных данных следует целое положительное число n (1 ≤ n ≤ 100 000) — количество отрезков, нарисованных Викой.
В следующих n строках заданы по четыре целых числа x1, y1, x2, y2 ( - 109 ≤ x1, y1, x2, y2 ≤ 109) — координаты концов отрезков, нарисованных Викой. Гарантируется, что все отрезки параллельны осям координат. Отрезки могут пересекаться, накладываться друг на друга и даже полностью совпадать.
Выведите количество закрашенных Викой клеток. Если клетка была покрашена более одного раза, то в ответе она должна быть посчитана ровно один раз.
3
0 1 2 1
1 4 1 2
0 3 2 3
8
4
-2 -1 2 -1
2 1 -2 1
-1 -2 -1 2
1 2 1 -2
16
В первом тестовом примере Вика закрасит клетки (0, 1), (1, 1), (2, 1), (1, 2), (1, 3), (1, 4), (0, 3) и (2, 3).
| Codeforces Round 337 (Div. 2) |
|---|
| Закончено |
