|
Задача Pencils
Журналіст С.Паскаліс та програміст Б .Пітоннік, які
стали добрими друзями після спільної роботи над
проблемою з задачі AreaPlus, вирішили разом провести час
за кухлем пива. Коли пиво було випито, Паскаліс, маючи
два однакові набори олівців різної довжини, з кожного з
цих наборів виклав на столі дві різних фігури за таким
правилом: в кожному з «малюнків» не було спільної
частини, що має ненульову довжину для будь-якої пари
олівців, тобто олівці могли перетинатися, але не
накладалися один на одного. Паскаліс запрпонував
Пітонніку, перекладаючи олівці в одному з «малюнків»
отримати другий з точністю до паралельного переносу,
зробивши мінімальну кількість перекладань. Допоможіть
йому, адже, як відомо пиво погано впливає на мислення.
Технічні умови. Програма читає з клавіатури число
N (1
(1<=N<=1000) – кількість олівців в кожному з наборів. В
наступних N четвірках цілих чисел записані
координати x1i, y1i, x2i, y2i початку та кінця
відповідного олівця, Наступні N четвірок чисел описують
другий набір олівців в тому ж форматі. Всі координати за
абсолютною величиною не перевищують 10000 . Всі олівці
мають ненульову довжину (тобто x1i <> x2i або
y1i <> y2i ). Програма виводить на екран єдине число –
шукану величину.
Приклад
Введення
5 0 0 1 2 1 0 0 2 2 0 2 2 4 0 3 2 4 0 5 2 9 -1 10 1 10 1 9 3 8 1 10 1 8 1 9 -1 8 1 9 3
Виведення
3
Задача Pencils
Журналист С.Паскалис и программист Б .Питонник, ставшие
верными друзьями после совместной работы над задачей
AreaPlus, решили вместе провести время за кружкой пива.
Когда пиво было выпито, Паскалис, имея два одинаковых
набора карандашей разной длины, из каждого набора сложил
на столе две разных фигуры согласно следующему правилу:
в каждом из «рисунков» не было общей части, имеющей
ненулевую длину для любой пары карандашей, то есть
карандаши могли пересекаться, но не накладывались друг
на друга. Паскалис предложил Питоннику, перекладывая
карандаши в одном из «рисунков», получить другой с
точностью до параллельного переноса, сделав минимальное
количество перекладываний. Помогите ему, ведь, как
известно, пиво плохо влияет на мышление.
Технические условия. Программа читает с клавиатуры число
N (1 <= N <= 1000) – количество карандашей в каждом из
наборов. В последующих N четверках целых чисел записаны
координаты x1i, y1i, x2i, y2i начала и конца
соответствующего карандаша, следующие N четверок чисел
описывают второй набор карандашей в том же формате. Все
координаты по абсолютной величине не превосходят
10000.
Все карандаши имеют ненулевую длину (то есть
x1i <> x2i
или y1i <> y2i). Программа выводит на экран единственное
число – искомую величину.
Пример
Ввод
5 0 0 1 2 1 0 0 2 2 0 2 2 4 0 3 2 4 0 5 2 9 -1 10 1 10 1 9 3 8 1 10 1 8 1 9 -1 8 1 9 3
Вывод
3 |
