Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 32 Мб Сложность: 65%)

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
15
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

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru



Детальная информация купить диплом Уфа у нас.