|
Тетрис 3D
(Время: 3 сек. Память: 256 Мб Сложность: 58%)
Всем известна игра «Тетрис». Рассмотрим её трёхмерную версию, где в качестве падающих блоков будут выступать прямоугольные параллелепипеды, грани которых параллельны осям координат, а вершины имеют целочисленные координаты. Разумеется, при этом никакие два блока не могут пересекаться, но могут касаться.
Стакан, в который падают блоки, имеет вид прямоугольного параллелепипеда, основание которого имеет размер W×L. При этом один из углов основания находится в начале системы координат, а другой имеет координаты (W, L). Стены стакана параллельны осям координат.
Нам представлен некоторый момент игры, в которой положение N блоков зафиксировано. Известно, что блоки, полностью закрывающие горизонталь ненулевого объема уничтожаются, причем за наименьшее количество уничтоженных при этом блоков игрок получает большее количество очков.
Требуется написать программу, которая позволяет выбрать минимальное число блоков, которые образуют перекрытие по горизонтали, либо определить, что этого сделать невозможно.
Входные данные
В первой строке входного файла INPUT.TXT указаны три целых числа: N – количество блоков (1 ≤ N ≤ 105) и размеры стакана W и L (1 ≤ W, L ≤ 104). Каждая из последующих N строк описывает один блок, определяемый координатами противоположных углов: (x1, y1, z1) и (x2, y2, z2), при этом 0 ≤ x1 < x2 ≤ W, 0 ≤ y1 < y2 ≤ L, 0 ≤ z1 < z2 ≤ 109. Все числа во входном файле целые и разделяются пробелами или переводами строк.
Гарантируется, что блоки не пересекаются друг с другом.
Выходные данные
Первая строка выходного файла OUTPUT.TXT должна содержать либо слово «YES», если искомый набор блоков существует, иначе – слово «NO». В первом случае во второй строке следует вывести минимальное число блоков, образующих перекрытие по горизонтали, а в третьей строке – номера этих блоков согласно порядку, в котором они перечислены во входных данных.
Если возможно несколько минимальных наборов блоков, выведите любой из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 10 10
0 0 6 5 10 7
5 0 5 10 10 8
0 5 1 5 10 6 | YES
2
1 2 |
| 2 | 2 10 10
0 0 6 5 10 7
5 0 5 9 10 8 | NO |
Система оценки
Решения, работающие верно только в случае, когда все числа во входных данных не превышают 100, будут оцениваться в 40 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
