Олимпиадный тренинг

Задача . Crazy Fences


Задача

Темы: графы

После посещения музея современного искусства, ФД решил переупорядочить его ферму перемещением всех его N (1 <= N <= 500) изгородей между пастбищами. Каждая изгородь - горизонтальный или вертикальный отрезок на 2D-плоскости. Если две изгороди встречаются, то они делают это только в своих конечных точках.
У ФД имеется C (1 <= C <= 500) коров. Каждая корова находится на ферме и не в изгороди. Кроме того, никакие две коровы не находятся в одной точке. Две коровы называются принадлежащими одному и тому же сообществу, если они могут пройти одна к другой, не касаясь никаких изгородей.
Пожалуйста, помогите ФД определить размер самого большого сообщества.
PROBLEM NAME: crazy
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и C.
* Строки 2..1+N: Каждая строка содержит 4 целых числа x1, y1, x2, y2. Эти числа описывают изгородь из точки (x1,y1) в точку (x2,y2). Каждая изгородь или вертикальна (x1=x2) или горизонтальна (y1=y2). Все координаты в диапазоне 0 .. 1,000,000.
* Строки 2+N..1+N+C: Каждая строка содержит два целых числа x и y, описывающих корову в позиции (x,y). Все координаты в диапазоне 0 .. 1,000,000.
Формат выходных данных
* Строка 1: Количество коров в самом большом сообществе.
Примечание
Коровы #1 и #2 принадлежат одному и тому же сообществу, поскольку они могут навестить друг друга, не касаясь никаких изгородей. Корова #3 не может посетить корову #1 или корову #2 не перелезая через изгородь.
Примеры
№Входные данныеВыходные данные
1 
7 3
0 0 10 0
10 0 10 5
12 5 10 5
10 5 1 5
12 5 12 7
0 7 12 7
0 7 0 0
3 4
6 6
17 3
 
2
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет