В одном городе недавно запустили автобусную сеть. Однако, плата за проезд для жителей этого города показалась чрезмерной. И несознательные граждане, вместо того, чтобы покупать билет, стали договариваться с водителем и ездить за полцены. Конечно, городская казна понесла серьезные убытки, и было решено взять на работу нескольких контролёров. По уставу, каждый контролёр должен стоять на одном месте и останавливать подозрительные автобусы с целью проверки билетов.
Для повышения эффективности труда контролёров начальство хочет, чтобы через каждую точку, в которой находится контролёр, проходили маршруты всех автобусов. С другой стороны, нельзя ставить нескольких контролёров в одной точке, чтобы они не отвлекались от выполнения своих обязанностей. Наконец, третья сторона, независимый профсоюз, требует от городской администрации принять на работу максимальное количество контролёров.
Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.
На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.
Выведите в выходной файл одно число – максимальное количество контролёров, которые смогут обрести работу благодаря этому мероприятию.
1 0 0 1 1
4
Петя и его друг Андрейка только что познакомились с китайской мифологией. Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь: этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной. Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал перпендикулярно поверхности. Удержать равновесие дракон может только тогда, когда существуют две его различные точки, касающиеся стола, такие что центр масс дракона находится строго между ними.
Вам требуется узнать, сколько было устойчивых положений у дракона, в которых он мог сохранять равновесие во время сна, если известно, что форма ломаной в виде которой дракон спит всегда одна и та же.
В первой строке входного файла содержится число \(n\) (3 ≤ \(n\) ≤ 1000) – количество вершин ломаной и два целых числа \(x_c\) и \(y_c\) – координаты центра масс дракона (-1000 ≤ \(x_c\), \(y_c\) ≤ 1000). В следующих \(n\) строках содержится по два целых числа \(x_i\) и \(y_i\) (-1000 ≤ \(x_i\), \(y_i\) ≤ 1000) – координаты вершин ломаной в порядке обхода против часовой стрелки (ось \(O_X\) направлена вправо, а ось \(O_Y\) – вверх).
В первой строке выходного файла выведите число устойчивых положений дракона.
12 1 2 3 4 2 4 2 3 1 3 1 4 0 4 0 0 1 0 1 1 2 1 2 0 3 0
4