| Codeforces Round 269 (Div. 2) |
|---|
| Закончено |
Белые медведи Меньшиков и Услада из Санкт-Петербургского зоопарка и слоник Хорас из Киевского зоопарка решили заняться живописью. В рамках создания своего первого шедевра они уже нарисовали на бумаге эскиз, который состоит из n отрезков. Каждый отрезок был либо горизонтальный, либо вертикальный. Теперь друзья хотят упростить этот эскиз, стерев некоторые отрезки или части отрезков, так чтобы окончательное творение удовлетворяло трем условиям:
- Хорас хочет иметь возможность нарисовать всю картину, поставив кисть на холст только один раз и не отрывая ее, пока картина не будет закончена (нет ничего плохого в том, чтобы при этом провести кистью несколько раз по одному месту). Поэтому все оставшиеся отрезки должны образовывать единую связную фигуру.
- Меньшиков хочет, чтобы получившаяся фигура была простой. Простой фигурой он называет фигуру, которая не содержит ни одного цикла.
- Изначально все отрезки на эскизе имеют целочисленные координаты точек начала и конца. Услада не любит вещественные координаты и хочет, чтобы это условие выполнялось и после стирания.
Так как в остальном их эскиз уже прекрасен, то друзья решили стереть такие части эскиза, чтобы максимизировать сумму длин оставшихся отрезков. От вас требуется посчитать эту максимальную сумму длин оставшихся после стирания отрезков.
В первой строке входных данных находится целое число n (1 ≤ n ≤ 2·105) — количество отрезков на эскизе. В следующих n строках находятся по четыре числа x1, y1, x2, y2 ( - 109 ≤ x1 ≤ x2 ≤ 109; - 109 ≤ y1 ≤ y2 ≤ 109) — две координаты начала и две координаты конца отрезка. Все отрезкы не вырождены и являются либо строго горизонтальными, либо строго вертикальными.
Никакие два горизонтальных отрезка не имеют общих точек. Никакие два вертикальных отрезка не имеют общих точек.
Выведите единственное целое число — максимальную сумму длин оставшихся отрезков.
2
0 0 0 1
1 0 1 1
1
4
0 0 1 0
0 0 0 1
1 -1 1 2
0 1 1 1
5
Фигуры, которые можно получить в двух данных примерах:
В первом примере необходимо стереть любой из отрезков, так как два отрезка вместе не образуют единую связную фигуру.
Во втором примере изначальные отрезки образуют цикл, есть четыре способа разорвать этот цикл — стереть первый, второй или четвертый отрезок полностью или стереть середину третьего отрезка. Последний вариант изображен на рисунке.
