eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

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

Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.

prb2222

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

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

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

В первой строке содержится количество спичек n (1n1000) в каждом из изображений.

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

Все координаты по абсолютной величине не превосходят 104. Все спички имеют ненулевую длину, то есть x1ix2i или y1iy2i.

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
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
Çıxış verilənləri #1
3
Mənbə 2006, XIV Командный чемпионат школьников Санкт-Петербурга по программированию, 6 ноября, Задача F