Задача «Стеклянный забор» РОИ 2008 Автор задачи: Г еоргий Александрович Корнеев Разбор: М ихаил Эдуардович Дворкин. - презентация

1 Задача «Стеклянный забор» РОИ 2008 Автор задачи: Г еоргий Александрович Корнеев Разбор: М ихаил Эдуардович Дворкин

2 Граница болота многоугольник.

3 Рассмотрим вершины с наибольшим x. Среди них с наибольшим и наименьшим у. Отрезок, соединяющий их, сторона забора.

4 Аналогично находится верхняя, левая и нижняя сторона забора.

5 Задача разбивается на четыре построить участки забора между этими четырьмя сторонами. Эти четыре задачи аналогичны.

6 Построим участок забора между правой и верхней стороной. Ясно, что он выглядит так: Действительно, в заборе не может быть следующих конфигураций:

7 Рассмотрим две стороны забора. Внутри угла, образованного ими не должно быть вершин: Иначе вершина, лежащая там, окажется вне забора.

8 Допустим, мы достроили забор до некоторого момента. Какие две стороны будут следующими? Не может существовать точка С, такая что: x B y A Значит, B самая правая из всех точек, расположенных выше и левее А.

9 Правильное решение: отсортируем все точки по убыванию x, при равных x по убыванию y. Начиная с вершины 1, строим забор влево-вверх. Обрабатываем точки в порядке увеличения номера. Как только найдена точка с меньшим x и большим y, добавляем две стороны к забору.

10 Правильное решение: время работы O(n log n) естественно, 100 баллов. При построении забора можно каждую следующую точку искать за O(n), итого O(n 2 ) времени. Оценка 70 баллов. O(n 3 ) 40 баллов. «Попиксельный обход» 4050 баллов.