Порядок чтения двухколоночной страницы

Задание

Реализуйте функцию reading_order(boxes, width, height). Она получает рамки надписей, найденных движком на странице width × height, и возвращает их индексы в том порядке, в каком страницу читают.

boxes — список рамок, каждая рамка это кортеж (x1, y1, x2, y2) в пикселях: левый край, верхний, правый, нижний. Порядок рамок во входном списке — тот, в котором их отдал движок, то есть никакой.

Правила те же, что на прогоне урока.

Колонтитулы. Центр надписи по вертикали — (y1 + y2) / 2, без округления. Надпись считается верхним колонтитулом при центр < height * 0.1 и нижним при центр > height * 0.9. Сравнения строгие: надпись, чей центр пришёлся ровно на границу, относится к телу страницы.

Межколонник. Координата x занята, если её накрывает хотя бы одна надпись тела: x1 <= x <= x2. Колонтитулы в занятость не входят. Межколонник ищется среди координат от int(width * 0.3) до int(width * 0.7) включительно: это самая длинная непрерывная цепочка незанятых координат в этих пределах, причём цепочка, начавшаяся раньше, засчитывается только той частью, что лежит внутри. Если самых длинных несколько, берётся левая. Граница колонок — середина цепочки, (начало + конец) // 2. Если незанятых координат в этих пределах нет, страница одноколоночная.

Колонка. Надпись тела относится к левой колонке, если её центр по горизонтали (x1 + x2) / 2 не правее границы, и к правой в противном случае.

Порядок. Сначала верхние колонтитулы, затем левая колонка, затем правая, затем нижние колонтитулы. Внутри каждой группы надписи идут по возрастанию верхней координаты, при равной — по возрастанию левой, при равной — в порядке входного списка. На одноколоночной странице тело идёт одной группой между колонтитулами.

Пример

boxes = [
    (10, 2, 90, 6),     # колонтитул через всю ширину
    (10, 20, 45, 26),
    (55, 20, 92, 26),
    (10, 30, 45, 36),
    (55, 30, 92, 36),
    (40, 95, 60, 98),   # номер страницы
]
reading_order(boxes, 100, 100)
# [0, 1, 3, 2, 4, 5]

Тело занимает 10…45 и 55…92, свободна полоса 46…54, граница проходит по 50. Колонтитул тянется через всю ширину и полосу закрывает — потому занятость и считается без него.

Примечание

Вход уже разобран и приходит аргументами: список кортежей из четырёх целых и два целых числа. Координаты рамок лежат в пределах страницы, левый край меньше правого, верхний меньше нижнего. Менять входной список нельзя, в том числе сортировать его на месте. Вызывать функцию вручную не нужно, проверка запускает её сама.

Что проверяется

Код проверок скрыт, так что вот полный список того, что в них разбирается:

• формат ответа: список целых, в котором каждый индекс входного списка встречается ровно один раз;
• входной список после вызова не изменился;
• пример из условия;
• колонтитул тянется через межколонник — верхний и нижний;
• свободных полос несколько, разной ширины;
• две свободные полосы одинаковой ширины;
• свободная полоса за пределами поиска шире межколонника;
• надписи с одинаковой верхней координатой;
• центр надписи ровно на границе десятой части высоты — сверху и снизу;
• одноколоночная страница;
• страница из одних колонтитулов;
• одна надпись и пустой вход.