На плоскости задано N векторов. Есть 3 правила:
1) вектора на непересекающихся прямых можно сложить
2) вектора на одной прямой можно сложить (результат исходит из начала одного из векторов)
3) в любой точке можно породить два одинаковых по длине, но разнонаправленных вектора
Требуется найти эквивалентную данной систему, содержащую минимальное количество векторов.
На плоскости задано N векторов – направленных отрезков, для каждого из которых известны координаты начала и конца (вектор, у которого начало и конец совпадают, называется нуль-вектором, можно считать, что нуль-вектор лежит на любой прямой, которая через него проходит). Введем следующие три операции над направленными отрезками на плоскости:
1) Направленные отрезки ненулевой длины, лежащие на пересекающихся прямых, можно заменить на их сумму, причем единственным образом. В этом случае отрезки переносятся вдоль своих прямых так, чтобы их начала совпадали с точкой пересечения прямых, и складываются по правилу сложения векторов (правилу параллелограмма, при этом началом результирующего вектора является точка пересечения прямых).
2) Направленные отрезки, лежащие на одной прямой, также можно заменить на их сумму. Для этого один из отрезков (любой) нужно перенести в начало второго из них и сложить по правилу сложения векторов на прямой:
Это правило применимо и в случае, когда один из векторов, или даже оба, являются нуль-векторами.
Заметим, что если складываемые векторы противоположно направлены и имеют одну и ту же длину, то результатом их сложения является нуль вектор.
3) В любой точке плоскости можно породить два противоположно направленных отрезка равной (в том числе и нулевой) длины:
Будем говорить, что две системы векторов эквивалентны, если от одной системы можно перейти к другой с помощью конечной последовательности перечисленных выше операций.
Требуется получить любую систему векторов, эквивалентную заданной, состоящую из как можно меньшего числа векторов.
В первой строке входного файла записано число N – количество заданных векторов (1 < N ≤ 1000). В каждой из следующих N строк через пробел записаны четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты – целые числа, по модулю не превосходящие 1000.
В первой строке входного файла следует записать число M – количество векторов в полученной системе (1 ≤ M ≤ N). В каждой из следующих M строк через пробел должны находиться четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты – вещественные числа, записанные с 6 цифрами после точки.
3 1 1 1 3 3 3 3 1 5 1 7 1
1 3.000000 3.000000 5.000000 3.000000
2 2 4 5 10 -2 -4 -5 -10
1 2.000000 4.000000 2.000000 4.000000
Как и в обычном тетрисе, поле в игре Strategy Tetris представляет собой "стакан" шириной в W клеток (1W109) и бесконечной высоты. В этот стакан падают сверху N фигурок (1N100000). i-я фигурка представляет собой прямоугольник шириной в Wi клеток и высотой в одну клетку; самая левая клетка фигурки имеет абсциссу ai (1aiW–Wi+1). Фигурки падают по обычным правилам: если при падении фигурка хотя бы одной своей клеткой ложится на какую-либо уже упавшую фигурку, то ее движение прекращается.
В отличие от обычного тетриса, игрок не имеет возможности вращать фигурки или смещать их по горизонтали в процессе падения — еще бы, это пришлось бы делать быстро и не было бы времени серьёзно подумать над стратегией. Единственное, что он может — это выбрать порядок, в котором эти N фигурок упадут в стакан (каждая по одному разу). Ваша задача — помочь ему выбрать такой порядок, при котором высота образовавшейся в результате падения конструкции была бы как можно меньше. (В отличие от обычного тетриса, полностью заполненная фигурками горизонталь никуда не исчезает).
На рисунке ниже приведен пример заполнения стакана фигурками из примера входных данных (порядок заполнения соответствует выходному файлу, приведенному в примере).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 2 |
| |
| 1 | 3 | ||
В первой строке входного файла записаны числа N и W, а в последующих N строках — пары чисел ai и Wi.
Выведите в выходной файл минимальную возможную высоту конструкции, а затем последовательность номеров фигурок, к этой высоте приводящую. Фигурки нумеруются натуральными числами от 1 до N в том порядке, в котором они указаны во входных данных. Если возможных вариантов несколько, выведите любой из них.
3 4 1 2 2 2 3 2
2 3 1 2