Задача NewArea

Известная из задачи первого тура Area фирма «Элит-Окраина» вновь вышла на рынок торговли землей. И вновь они при продаже указывали неверные границы участков, хотя участки всегда имели форму прямоугольника с параллельными осям координат сторонами. Каждому покупателю продавалось не более одного участка. После завершения распродажи оказалось, что среди плативших за одну и ту же землю не только Юля Т. и Петя П. (а их участки, естественно, пересекались), но и другие их сотоварищи. Петя и Юля приняли решение из покупателей организовать партии, причем по новому принципу. Если два участка имели хотя бы одну общую точку, то их владельцы попадали в одну партию. В эту же партию попадали все владельцы участков, которые имели хотя бы одну общую точку с участком хотя бы одного ранее принятого партийца (границы принадлежат участкам). Естественно, партия Юли и Пети оказалась самой многочисленной. Однако по причинам, изложенным в задаче Area, они не смогли сосчитать количество членов своей партии. Помогите им и на этот раз.
Технические условия: Программа считывает с клавиатуры натуральное число N (2<=N<=200), а далее N групп по 4 целых числа – координаты противоположных вершин участков (-1000<Х`і`, У`і`<1000). Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число – искомую величину.
Пример:
Ввод
6 30 100 -40 120 60 40 40 90 -90 30 -20 - 40 -30 50 50 20 20 80 -20 110 -50 80 -70 20
Вывод 4

Задача Ferry

Участников полярной экспедиции, зимующих на льдине, постигло большое несчастье: льдина раскололась, и все они оказались на маленьком ее обломке. Нужно как можно быстрее переправиться через широкую трещину. В их распоряжении есть двуместная надувная лодка.Для каждого полярника известно время, необходимое ему для переправы на этой лодке через трещину. Если же в лодке находятся 2 полярника, время переправы равно
времени менее расторопного из них. За какое минимальное время все полярники могут переправиться на большую льдину?
Технические условия: Программа считывает с клавиатуры натуральное число N (3<=N<=10000) – количество полярников, а далее N натуральных чисел не больших 10000 – времена переправы каждого полярника. Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число – искомую величину.
Пример:
Ввод 4 1 6 7 8
Вывод 23

Задача Mayor

Мэр города Балдуйска решил вымостить городские тротуары плиткой. Каждой фирме достался кусок тротуара. Все тротуары в городе имеют ширину 3 метра. Завод, которым, как водится, владел «мэрский» сын, выпускал плитку 1x1 и 1x2 метра, а другую плитку, естественно, городские власти не закупали. Фирма «Балдстрой» получила задачу выстелить кусок тротуара длиной N метров. Сколькими разными способами они могут это сделать?
Технические условия: Программа читает с клавиатуры одно целое число N (2<=N<=1000) – длину тротуара. Программа выводит на экран единственное число – искомую величину.
Пример:
Ввод 2
Вывод 22

Задача Mayor2

Уже известный нам мэр Балдуйска решил уменьшить расходы на организацию автобусных маршрутов. Сам город имел N улиц, идущих строго с юга на север, и N пересекающих их улиц, идущих с запада на восток. Все улицы, естественно, одинаковой длины, а движение по ним одностороннее (т.е. ехать можно либо с юга на север, либо с запада на восток). Утром на некоторых перекрестках собираются люди. Их подбирают безразмерные автобусы, дабы отвезти на работу за город. Да вот одна маленькая проблема: все автобусы начинают свой маршрут с самого юго-западного перекрестка, Какое минимальное количество автобусов следует выпускать на маршрут утром, чтобы подобрать всех стоящих на перекрестках пассажиров?
Технические условия: Программа читает с клавиатуры два натуральных числа: N – количество улиц в каждом направлении (N<=1000), P – количество перекрестков с стоящими пассажирами (1<P<=1000000), а далее P групп по 2 числа – координаты перекрестка с пассажирами. Понятно, что "самый юго-западный перекресток имеет координаты (1,1) Все числа вводятся одной строкой через пробелы. Прoграмма выводит на экран единственное число – искомую величину.
Пример:
Ввод 8 8 3 1 4 2 7 3 2 4 5 4 3 6 4 7 7 6
Вывод 3

Задача Zigzag

Последовательность чисел называется зигзагом, если в ней нет ни одной монотонно невозрастающей и ни одной монотонно неубывающей подпоследовательности подряд идущих элементов длиной 3. Дана последовательность. Какое минимальное количество элементов необходимо вставить в нее, чтобы получился зигзаг?
Технические условия: Программа читает с клавиатуры количество элементов последовательности N (3<=N<=10000) и N чисел - элементы последовательности (не большие 1000 по абсолютной величине каждый). Все числа вводятся одной строкой через пробел. Программа выводит на экран единственное число – искомую величину.
Пример:
Ввод: 6 1 4 7 9 7 4
Вывод: 3

Г.Кравец, Г.Непомнящий, Ю.Пасихов А.Присяжнюк