Спички детям не игрушка!

Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение A, составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение B. Например, из римского числа XIV можно получить ромб с диагональю, переложив всего три спички.

Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении A, совпадает с набором спичек, используемым в изображении B. Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга). Вася устал решать головоломки вручную, и теперь он просит вас написать программу, которая будет решать головоломки за него. Программа будет получать описания изображений A и B и должна найти минимальное количество спичек, которые надо переложить в изображении A, чтобы полученная картинка получалась из B параллельным переносом.

Входные данные

В первой строке входного файла INPUT.TXT содержится целое число n – количество спичек в каждом из изображений (1 ≤ n ≤ 1000). В следующих n строках записаны координаты концов спичек на изображении A. Спичка номер i описывается целыми числами x₁i, y₁i, x₂i, y₂i координатами ее концов. Следующие n строк содержат описание изображения B в таком же формате. Набор длин этих спичек совпадает с набором длин спичек с изображения A. Все координаты по абсолютной величине не превосходят 10⁴. Все спички имеют ненулевую длину.

Выходные данные

Выведите в выходной файл OUTPUT.TXT минимальное количество спичек, которые следует переложить, чтобы изображение A совпало с изображением B, с точностью до параллельного переноса.

Пример

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

[Обсуждение] [Все попытки] [Лучшие попытки]