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

Презентация:



Advertisements
Похожие презентации
Стехов Игорь 10 класс. Отметить на линии синусов число а. Отметить все синусы, которые больше(меньше) числа а. Выделить на единичной тригонометрической.
Advertisements

Экономическа проблема Участок моряЭкономическа проблема Участок моря.
Правильные выпуклые п-угольники подобны. В частности, если у них стороны равны, то они равны. Докажем второе утверждение теоремы. А4А4 А2А2 А1А1 А3А3.
Конфигурации планет. Нижние планеты – планеты, орбиты которых находятся внутри земной.
Построение треугольника по 3 элементам. Разминка.
а) Для построения правильного шестиугольника можно воспользоваться тем, что а 6 = R. Построение. 1. Строим ω(О; R). О 2. Строим произвольную точку, принадлежащую.
УГЛЫ. РАЗВЕРНУТЫЙ УГОЛ. ПРЯМОЙ УГОЛ Автор : Еремеева Марина Валерьевна, учитель математики МОУ «Средняя общеобразовательная школа 25» г. Бийска Бийск,
Пирамида Пирамидой называется многогранник, который состоит из плоского многоугольника – основания пирамиды, точки, не лежащей в плоскости основания, -
ИСПОЛЬЗОВАНИЕ ИКТ НА УРОКАХ ГЕОМЕТРИИ ПРИ ИЗУЧЕНИИ ТЕМЫ «КОМБИНАЦИИ ГЕОМЕТРИЧЕСКИХ ТЕЛ» ПЕТРОВА ИРИНА ВЛАДИМИРОВНА идентификатор
Компьютерная геометрия и графика. Лекция 2. План занятия: Проверка многоугольника на выпуклость. Нахождение площади произвольного многоугольника. Принадлежность.
Две взаимно перпендикулярные числовые оси с общим началом 0 образуют прямоугольную систему координат на плоскости. Горизонтальная ось называется осью.
Диагонали многоугольника Свойства диагоналей. Диагональ многоугольника – это отрезок, соединяющий две несоседние вершины многоугольника.
Взаимное расположение прямых в пространстве. Угол между прямыми. Подготовила: Зайцева Марианна Учитель: Васюк Наталья Викторовна.
Окружность. Окружностью называется геометрическая фигура, состоящая из всех точек плоскости, расположенных на заданном расстоянии от данной точки, называемой.
Изопериметрическая задача Изопериметрической задачей называют задачу о нахождении фигуры наибольшей площади, ограниченной кривой заданной длины (периметра)
Многоугольники. Виды многоугольников. Внутренние и внешние углы выпуклого многоугольника. Сумма внутренних углов выпуклого n-угоьника (теорема). Сумма.
Треугольники. Задачи на построение.. Содержание: Определение Виды треугольника Первый признак равенства треугольников. Доказательство. Второй признак.
Отрезки, соединяющие не соседние вершины многоугольника, называются диагоналями многоугольника. А4А4 А2А2 А5А5 А1А1 А3А3 Рассмотрим простую ломаную А.
Ломаные Ломаной называется … фигура, образованная конечным набором отрезков, расположенных так, что … Сами отрезки называются…сторонами ломаной, а их концы.
Медиана. Биссектриса. Высота. В тупоугольном треугольнике две высоты падают на продолжение сторон и лежат вне треугольника. Третья внутри треугольника.
Транксрипт:

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

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

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

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

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

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

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

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

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

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