Зимняя школа по программированию, 2009

Зимняя школа по программированию, 2009.

Фрагмент из книги:
Введем на плоскости декартову систему координат Оху. Тогда каждая точка будет задаваться двумя координатами (х, у). Если будут заданы две точки, то их можно соединить отрезком. Направленный отрезок, соединяющий две точки А и В (причем А считается началом вектора), называется вектором - одна из этих точек определяет. При этом отождествляем параллельные векторы одинаковой длины, направленные в одну сторону (то есть рассматриваем свободные векторы).




Выпуклая оболочка.
Выпуклым называется такое множество точек плоскости, которое обладает тем свойством, что для любых двух точек, принадлежащих множеству, отрезок их соединяющий, целиком содержится в данном множестве.

Если же исходное множество не является выпуклым, то можно построить множество, содержащее исходное в качестве подмножества. Оказывается, что среди всех таких выпуклых множеств существует одно минимальное (в том смысле, что содержится в любом другом выпуклом множестве, содержащем исходное). Оно и называется выпуклой оболочкой исходного множества.

Если задано конечное множество точек, то, как не трудно увидеть, его выпуклой оболочкой будет многоугольник, вершинами которого будут точки исходного множества. Таким образом, задача построения выпуклой оболочки заключается в выделении таких точек и перечислении их в порядке обхода по контуру (например, против часовой стрелки).

ОГЛАВЛЕНИЕ.
День первый. Контест Виталия Неспирного и Антона Лунёва.
Об авторах.
Теоретический материал. Близость точек на плоскости.
Задачи и разборы.
Задача А. Выборы вождя.
Задача В. Покер.
Задача С. Каждый третий бесплатно.
Задача D. Распределение.
Задача Е. Кладбище.
Задача F. Продовольственная программа.
Задача G. Призыв в армию.
Задача Н. Родственники.
Задача I. Деление земель.
Задача J. Экстремальные расстояния.
Задача К. Наименьший квадрат.
Задача L. Вражда.
Задача М. Дирихле и Фибоначчи.
Задача N. Похожие слова.
Задача О. Экстремальный граф.
Задача Р. Попарные суммы.
Задача Q. Биномиальные коэффициенты.
Задача R. Биномиальные коэффициенты 2.
Задача S. Пирамида из чисел.
Задача Т. k-суммы с повторениями.
День второй. Контест Михаила Дворкина.
Об авторе.
Теоретический материал. Конечные автоматы и регулярные выражения.
Задачи и разборы.
Задача А. Минимизация ДКА.
Задача В. Обращение ДКА.
Задача С. ДКА, проверяющий делимость.
Задача D. Укладка плиток.
Задача Е. Непоглощающий ДКА.
Задача F. Распознавание конечного языка.
Задача G. Регулярное выражение.
Задача Н. Автомат-собеседник для Эллочки-людоедки.
Задача I. Минимизация ДКА.
Задача J. Обращение ДКА.
Задача К. ДКА, проверяющий делимость.
Задача L. Укладка плиток.
Задача М. Непоглощающий ДКА.
Задача N. Распознавание конечного языка.
Задача О. Регулярное выражение.
Задача Р. Автомат-собеседник для Эллочки-людоедки.
День третий. Контест Виталия Виталия Гольдштейна.
Об авторе.
Теоретический материал. Потоки в сетях.
Задачи и разборы.
Задача А. Дартс.
Задача В. Сочинитель стихов.
Задача С. Число инверсий.
Задача D. Директивы include.
Задача Е. Простецкие числа.
Задача F. Неточный поиск.
Задача G. Такси.
Задача Н. Великая стена.
Задача I. Разрез.
Задача J. Испорченный паркет.
День четвертый. Контест Виталия Гольдштейна.
Теоретический материал. Близость точек на плоскости.
Задачи и разборы.
Задача А. Мороженое.
Задача В. Коллекционирование монет.
Задача С. Уголки.
Задача D. Встроенная очередь команд.
Задача Е. Клуб “Двоичный кот”.
Задача F. Балансировка нагрузки.
Задача G. Охлаждение реактора.
Задача Н. Пешеходные зоны против кольцевых.
Задача I. Кони.
Задача J. Сложите многоугольник.
День пятый. Контест Михаила Медведева.
Об авторе.
Задачи и разборы.
Задача А. Одинаковые шары.
Задача В. Дни рождения.
Задача С. Толстая монета.
Задача D. Дуэлянты.
Задача Е. Лес.
Задача F. Счастливые пятерки.
Задача G. Произведение матриц.
Задача Н. Треугольники в многоугольнике.
Задача I. Обработка текста.
Задача J. Чемпионат мира.
День шестой. День Теодора Заркуа и его учеников.
Об авторе.
Теоретический материал.
Задачи и разборы.
Задача А. Максимальное число.
Задача В. Двоичные строки.
Задача С. Стрекоза и муравей.
Задача D. Кладоискатели.
Задача Е. Однажды в Китае.
Задача F. Возвращение Супермена.
Задача G. Нелюбимые цифры.
Задача Н. Шоколад.
Задача I. Похищение невесты.
Задача J. Сегменты.
Задача К. Шоколадная Фабрика.
Задача L. Строки.
Задача М. Стрекоза и муравей 2.
Задача N. Нелюбимые цифры 2.
Задача О. Снова палиндромы.
Задача Р. Преобразование.
Задача Q. Равносильность.
Задача R. Однажды в Китае 2.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Зимняя школа по программированию, 2009 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование