Vika47696

09.11.2020 21:36 •  Информатика

Наклейки Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Айтал — успешный спортивный программист. В течение года он принял участие в n олимпиадах.
На каждой олимпиаде он получал комплект мерча, состоящий из блокнота, ручки и наклейки.
Блокноты и ручки Айтал использует для учебы, а наклейки он решил клеить на ноутбук.
В конце года некоторые наклейки оказались перекрыты другими. Айтал захотел узнать, сколько
неперекрытых наклеек на его ноутбуке.
Представим поверхность ноутбука в виде декартовой системы координат с центром в левом
нижнем углу, а наклейки — в виде прямоугольников со сторонами, параллельными осям координат.
Формат входных данных
В первой строке записано одно целое число n (1 6 n 6 1000) — количество наклеек.
В следующих n строках даны по четыре целых числа x1, y1, x2, y2
(0 6 x1 < x2 6 109
, 0 6 y1 < y2 6 109
) — координаты левого нижнего и правого верхнего
углов прямоугольника, описывающего каждую наклейку. Описание наклеек дано на вход в порядке
приклеивания их на ноутбук.
Формат выходных данных
В первой строке выведите одно целое число — искомое количество наклеек.
Во второй строке выведите через пробел номера неперекрытых наклеек в порядке следования
во входных данных. Наклейки нумеруются с 1.
Система оценки
за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
Подзадача Дополнительные
ограничение
Необходимые
подзадачи
Информация о
проверке
1 15 1 6 n, x2 6 100,
y1 = 0, y2 = 1 (все
прямоугольники
имеют высоту 1)
полная
2 25 1 6 n, x2, y2 6 100 У, 1 полная
3 60 У, 1, 2 полная
Примеры
стандартный ввод стандартный вывод
5
0 0 1 1
1 1 3 3
3 3 4 4
0 0 2 2
2 2 4 4
2
4 5
5
0 0 2 2
2 2 4 4
0 0 1 1
1 1 3 3
3 3 4 4
3
3 4 5