Оформление (100 баллов)
Задачу добавил: alef
Успешно сдано решений: 10
Когда в комнате такие оригинальные обои, то хочется, чтобы и стены в лоджии выглядели соответственно. Для «оформления» лоджии были приобретены панели разных цветов, из которых предполагается собрать на стене оригинальный узор. Панели были разрезаны на прямоугольные полоски. По мере разрезания полоски нумеровали (последовательно) и складывали на прямоугольный стол (тоже последовательно, по порядку номеров) таким образом, чтобы стороны полосок и стола были параллельны. Полоски могли быть уложены друг на друга, но под уже имеющиеся их не подсовывали.
Наконец, все полоски нарезаны, и теперь все готово к монтажу. А начинать его надо с полоски № 1, которая была отрезана и уложена на стол самой первой...
Ваша задача – написать программу, подсчитывающую, какое наименьшее количество полосок нужно снять, чтобы освободить первую полоску. Кроме того, нужно определить порядок, в котором должны сниматься полоски.
Пояснение. Полоску можно снять только тогда, когда никакая ее часть не накрыта другой полоской (касание допускается)
Формат входного файла input.txt
Первая строка – целое число N (1<=N<=100) – количество полосок
Каждая из следующих N строк содержит целочисленные координаты x, y двух противоположных вершин полоски (|x|<=10000, |y|<=10000) с соответствующим номером (вторая строка содержит координаты полоски № 1, третья – полоски № 2, …, N+1 строка – полоски № N)
Формат выходного файла output.txt
Первая строка – целое число S – количество полосок, которые необходимо снять
Вторая строка – S целых чисел через пробел – номера полосок, определяющих порядок, в котором их нужно снимать. Если возможно несколько решений, вывести то, в котором полоски снимаются по убыванию их номеров.
Пример входного файла
3
0 0 3 10
5 5 1 1
7 6 –2 9
Пример выходного файла
2
3 2
Пояснение к выходному файлу
На рисунке приведено расположение полосок на столе (границы стола показаны жирной линией; впрочем, для решения задачи местоположение границ стола значения не имеет)