시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение $A$, составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение $B$.
Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.
Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении $A$, совпадает с набором спичек, используемым в изображении $B$. Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).
Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений $A$ и $B$ и должна найти минимальное количество спичек, которые надо переложить в изображении $A$, чтобы полученная картинка получалась из $B$ параллельным переносом.
В первой строке входного файла содержится целое число $n$ --- количество спичек в каждом из изображений ($1 \le n \le 1000$).
В следующих $n$ строках записаны координаты концов спичек на изображении $A$. Спичка номер $i$ описывается целыми числами $x_{1i}$, $y_{1i}$, $x_{2i}$, $y_{2i}$ --- координатами ее концов. Следующие $n$ строк содержат описание изображения $B$ в таком же формате. Набор длин этих спичек совпадает с набором длин спичек с изображения $A$.
Все координаты по абсолютной величине не превосходят $10^4$. Все спички имеют ненулевую длину, то есть $x_{1i} \ne x_{2i}$ или $y_{1i} \ne y_{2i}$.
Выведите в выходной файл минимальное количество спичек, которые следует переложить, чтобы изображение $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