Кількість цвяхів
Кількість цвяхів
На квадратному столі розкладено N
прямокутних аркушів паперу, сторони у яких паралельні границям стола. Відомо цілі координати пар протилежних вершин кожного прямокутника у системі координат, центр якої лежить в одній з вершин стола, осі проходять через дві перпендикулярні границі столу.
Потрібно підрахувати мінімальну кількість цвяхів, необхідних для того, щоб прибити всі аркуші до столу. Аркуш вважається прибитим, якщо в середині нього проходить хоча б один цвях (цвяхи, що проходять через границі аркушу, не прибивають його).
Вхідні дані
В першому рядку число N
(1 ≤ N ≤ 20
). У наступних N
рядках по чотири невід’ємних цілих числа – координати двох протилежних вершин кожного прямокутника, числові значення не перевищують 100.
Вихідні дані
Одне число – мінімальна кількість використаних цвяхів.
3 2 2 5 6 3 3 7 1 6 4 4 7
2