Задача
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
Задача
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 |
