Спички детям не игрушки!
Спички детям не игрушки!
Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение A, составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение B.
Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.
Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении A, совпадает с набором спичек, используемым в изображении B. Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).
Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений A и B и должна найти минимальное количество спичек, которые надо переложить в изображении A, чтобы полученная картинка получалась из B параллельным переносом.
Входные данные
В первой строке содержится количество спичек n (1 ≤ n ≤ 1000) в каждом из изображений.
В следующих n строках записаны координаты концов спичек на изображении A. Спичка номер i описывается целыми числами x1i
, y1i
, x2i
, y2i
– координатами ее концов. Следующие n строк содержат описание изображения B в таком же формате. Набор длин этих спичек совпадает с набором длин спичек с изображения A.
Все координаты по абсолютной величине не превосходят 104
. Все спички имеют ненулевую длину, то есть x1i
≠ x2i
или y1i
≠ y2i
.
Выходные данные
Выведите минимальное количество спичек, которые следует переложить, чтобы изображение A совпало с изображением B с точностью до параллельного переноса.
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