Пронести в проём
Плоскую деталь — столешницу, лист фанеры, вырезанный контур — нужно пронести через узкий проём, держа её в плоскости проёма и не поворачивая, пока она проходит. Повернуть её заранее можно как угодно. Какой самый узкий проём для неё достаточен? И второй вопрос от того же мастера: из какого наименьшего по площади прямоугольного листа можно вырезать эту деталь?
Контур детали задан точками — вершинами её границы, возможно вперемешку с точками внутри, повторами и точками на сторонах. Деталь — это всё, что внутри границы, поэтому для ответа достаточно точек.
Вход
В первой строке — n (3 ≤ n ≤ 2 · 105). Дальше n строк: целые координаты x y, |x|, |y| ≤ 106. Не все точки лежат на одной прямой.
Выход
Два числа через пробел: ширину самого узкого проёма и площадь наименьшего прямоугольника. Ответ засчитывается, если ошибка каждого числа не больше 10−6, а для чисел больше единицы — не больше 10−6 от ответа.
Примеры
Пример 1
3 0 0 4 0 0 3
2.400000000 12.000000
Пример 2
6 0 0 3 3 0 6 -3 3 0 3 1 3
4.242640687 18.000000
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проём, через который деталь проходит, — это полоса между двумя параллельными прямыми. Нужна самая узкая полоса, в которую деталь помещается целиком. Важна только выпуклая оболочка точек: полоса и прямоугольник выпуклы, и если в них лежат точки, лежит и оболочка.
2Подсказка 2
Направлений бесконечно много, но перебирать их все не нужно. У самой узкой полосы одна сторона лежит на стороне оболочки, у наименьшего прямоугольника — тоже. Значит, кандидатов столько же, сколько сторон оболочки.
3Идея
Вращающиеся калиперы. Для каждой стороны оболочки нужны три вершины: самая далёкая от прямой стороны — она даёт ширину полосы — и две крайние вдоль стороны — они дают длину прямоугольника. Когда переходим к следующей стороне, все три вершины сдвигаются только вперёд по обходу оболочки, поэтому на все стороны уходит O(h) шагов.
4Разбор
Оболочка — алгоритм Эндрю, против часовой стрелки, без точек на сторонах. Для стороны AB с вектором e: высота вершины P — векторное произведение (B − A) × (P − A), положение вдоль стороны — скалярное e · (P − A). Самая далёкая вершина j двигается, пока следующая выше; правая крайняя r — пока следующая дальше вдоль e; левая l — пока следующая дальше в обратную сторону. Начальные положения для первой стороны: r от нулевой вершины, j от r, l от j. Ширина полосы — высота / |e|, площадь — высота · (длина вдоль e) / |e|². Все сравнения при движении — в целых числах.
4+Решение
5Сложность
O(n log n) на оболочку и O(h) на калиперы, где h — число её вершин. На окружности из двухсот тысяч точек в оболочке 11 744 вершины — остальные после округления до целых попали внутрь или на стороны, — и перебор «сторона против всех вершин» — O(h²) — уже не успевает.
6Типичные ошибки
- Перебор. Это
wrong.py: на тысяче случайных точек в оболочке 16 вершин, и он успевает; на окружности — нет. - Прямоугольник вдоль осей. Для треугольника из первого примера он случайно оптимален, для квадрата, стоящего на углу, — вдвое больше нужного.
- Диаметр вместо ширины. Самая далёкая пара точек определяет, какой длины нужен проём, если нести деталь вдоль; ширина — минимум по направлениям, а не максимум.
- Точки на сторонах оболочки. Если оставить их, у оболочки появятся стороны нулевого поворота; калиперы с ними работают, но строгие сравнения при движении упоров должны это допускать. Проще выбросить их при построении.
Алгоритмы задачи
O(n) после оболочки, O(n log n) с ней
2 задачи
GEO
Алгоритм
Выпуклая оболочка
Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n).
O(n log n)
2 задачи