e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Количество гвоздей

Количество гвоздей

prb4199 На квадратном столе разложено N прямоугольных листков бумаги, стороны у которых параллельны сторонам стола. Известны целые координаты пар противоположных вершин каждого прямокугольника в системе координат, центр которой лежит в одной из вершин стола, оси проходят через две перпендикулярные границы стола.

Нужно посчитать минимальное количество гвоздей, необходимых для того, чтобы прибить все листки к столу. Листок считается прибитым, если в середине его проходит хотя бы один гвоздь (гвозди, проходящие через границы листка, не прибивают его).

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

В первой строке число N (1N20). В последующих N строках по четыре неотрицательных целых числа – координаты двух противоположных вершин каждого прямоугольника, все числовые значения не превышают 100.

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

Одно число – минимальное количество использованных гвоздей.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3
2 2 5 6
3 3 7 1
6 4 4 7
Output example #1
2