Подразделы

Дата и время

05/12/2024 02:49:11

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЛето 6

printA. Автобусы

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В одном городе недавно запустили автобусную сеть. Однако, плата за проезд для жителей этого города показалась чрезмерной. И несознательные граждане, вместо того, чтобы покупать билет, стали договориваться с водителем и ездить за полцены. Конечно, городская казна понесла серьезные убытки, и было решено взять на работу нескольких контролёров. По уставу, каждый контролёр должен стоять на одном месте и останавливать подозрительные автобусы — с целью проверки билетов.
Для повышения эффективности труда контролёров начальство хочет, чтобы через каждую точку, в которой находится контролёр, проходили маршруты всех автобусов. С другой стороны, нельзя ставить нескольких контролёров в одной точке, чтобы они не отвлекались от выполнения своих обязанностей. Наконец, третья сторона, независимый профсоюз, требует от городской администрации принять на работу максимальное количество контролёров.
Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.
На первой строке ввода находится число `n` (`1\ ≤\ n\ ≤\ 10^4`) — количество маршрутов. Далее следуют `n` строк, на каждой из которых находятся две пары целых чисел — координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят `10^8` по абсолютной величине.
Выведите в выходной файл одно число — максимальное количество контролёров, которые смогут обрести работу благодаря этому мероприятию.

Пример ввода

2
0 0 2 2
1 0 4 2

Пример вывода

4
Источник: XI командный чемпионат школьников Санкт-Петербурга по программированию
loading