Олимпиадный тренинг

Задача . C. Диванный вор


Задача

Темы: Перебор реализация *2000

Скоро начинается очередной раунд на DecoForces! Дедушка Макс хотел поучаствовать в раунде, но за 15 минут до начала обнаружил пропажу — кто-то украл его любимый диван, на котором он писал контесты.

К счастью, вор оставил записку для дедушки Макса. Записка привела его на склад диванов. Но вот незадача — дедушка не может определить, какой из диванов был украден у него, так как внешне они все одинаковые!

Представим склад как прямоугольное поле n × m клеток. Каждый диван занимает две клетки склада, соседние по стороне. Каждую клетку занимает не более одного дивана (но могут быть и пустые клетки).

Считается, что диван A расположен левее дивана B, если существуют две таких клетки a и b, что a принадлежит дивану A, b принадлежит дивану B, и xa < xb. Диван A расположен выше дивана B, если существуют две таких клетки a и b, что a принадлежит дивану A, b принадлежит дивану B, и ya < yb. Аналогично определяем, когда какой-то диван правее или выше другого.

Обратите внимание, что во всех условиях выполняется A ≠ B. Также диван A может одновременно быть и выше другого дивана B, и ниже него. То же для левого и правого условий.

В записке, которую нашёл дедушка Макс, указывалось, что левее его дивана расположено cntl диванов, правее — cntr диванов, выше — cntt диванов и ниже — cntb диванов.

Помогите дедушке по этим данным найти его диван! Гарантируется, что не более одного дивана подходит под заданные условия.

Выведите номер дивана дедушки Макса. Если нет такого дивана, что все условия соблюдаются, то выведите -1.

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

В первой строке записано целое число d (1 ≤ d ≤ 105) — количество диванов на складе.

Во второй строке записаны два числа n, m (1 ≤ n, m ≤ 105) — размеры склада.

В следующих d строках записано по четыре целых числа x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — координаты i-го дивана. Гарантируется, что клетки (x1, y1) и (x2, y2) имеют общую сторону, (x1, y1)  ≠  (x2, y2) и ни одна клетка не покрыта более чем одним диваном.

В последней строке записаны четырех целых числа cntl, cntr, cntt, cntb (0 ≤ cntl, cntr, cntt, cntb ≤ d - 1).

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

Выведите номер дивана, для которого все условия соблюдаются. Диваны пронумерованы от 1 до d в порядке входных данных. Если такого дивана нет, то выведите -1.

Примечание

Рассмотрим второй пример.

  • У первого дивана 0 расположены слева от него, 2 справа (1, 1) находится слева и от (5, 5), и от (5, 4)), 0 сверху и 2 снизу (и 2-й, и 3-й диваны находятся ниже).
  • У второго дивана cntl = 2, cntr = 1, cntt = 2 and cntb = 0.
  • У третьего дивана cntl = 2, cntr = 1, cntt = 1 and cntb = 1.

Второй диван подходит под данные условия.

В третьем примере:

  • У первого дивана cntl = 1, cntr = 1, cntt = 0 and cntb = 1.
  • У второго дивана cntl = 1, cntr = 1, cntt = 1 and cntb = 0.

И так как нет ни одного дивана с набором (1, 0, 0, 0), то ответ -1.


Примеры
№Входные данныеВыходные данные
1 2
3 2
3 1 3 2
1 2 2 2
1 0 0 1 
1
2 3
10 10
1 2 1 1
5 5 6 5
6 4 5 4
2 1 2 0 
2
3 2
2 2
2 1 1 1
1 2 2 2
1 0 0 0 
-1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет