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

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

Фрагмент из книги:
Для точки на сфере существует единственная диаметрально ей противоположная точка на сфере. Таким образом, все точки сферы делятся на пары диаметрально противоположных точек.
Прямой на сфере назовем замкнутую линию на сфере, лежащую в некоторой плоскости, проходящей через центр сферы. Через две точки, не являющиеся диаметрально противоположными, можно провести единственную прямую. Будем отождествлять прямую на сфере с плоскостью, в которой эта прямая лежит. Отрезком назовем непрерывную замкнутую часть прямой (дуга окружности).




Задача Е. Выпуклая оболочка 3D - 1.
Имя входного файла: е. in
Имя выходного файла: е. out
Ограничение по времени: 1 с
Ограничение по памяти: 256 Мб

Даны n точек в пространстве. Никакие 4 точки не лежат в одной плоскости. Найдите выпуклую оболочку этих точек.

Формат входного файла.
Первая строка содержит число m — количество тестов. В последующих строках описаны сами тесты. Каждый тест начинается со строки, содержащей nп (1 < n < 1000) — число точек. Далее, в n строках даны по три числа — координаты точек. Все координаты целые, не превосходят по модулю 500. Общее количество точек не превосходит 22000.

Формат выходного файла.
Для каждого теста выведите следующее. В первую строку выведите количество граней т. Далее в последующие т строк выведите описание граней: количество вершин и номера точек в исходном множестве. Точки нумеруются в том порядке, в котором они даны во входном файле. Точки в пределах грани должны быть отсортированы в порядке против часовой стрелки относительно внешней нормали к грани.

ОГЛАВЛЕНИЕ.
День первый. Контест Пака Станислава Олеговича.
Об авторе.
Теоретический материал. 3D-геометрия.
Задачи и разборы.
Задача А. Касательные к сферам.
Задача В. Расстояние между отрезками.
Задача С. Конусы.
Задача D. Снайпер.
Задача Е. Выпуклая оболочка 3D - 1.
Задача F. Прямые.
Задача G. Взаимное расположение прямых.
Задача Н. Выпуклая оболочка 3D - 2.
Задача I. Выпуклая оболочка 3D - 3.
Задача J. Расстояние от точки до отрезка.
Задача К. Цилиндр.
Задача L. Разрежем арбуз.
День второй. Контест Жукова Дмитрия Ивановича.
Об авторе.
Теоретический материал. Алгоритм Карацубы. Быстрое преобразование Фурье.
Задачи и разборы.
Задача А. ДНК роботов.
Задача В. Треугольник.
Задача С. Монеты.
Задача D. Уравнение.
Задача Е. Разворот битов.
Задача F. АВЛ-деревья.
Задача G. Многочлен.
Задача Н. Раздвоение.
Задача I. Уравнение 2.
Задача J. Разворот битов 2.
Задача К. Дуэль.
Задача L. Произведение.
Задача М. Сфера.
День третий. Контест Дворкина Михаила Эдуардовича.
Об авторе.
Теоретический материал. Динамическое программирование по профилю и по изломанному профилю.
Задачи и разборы.
Задача А. Треугольный король.
Задача В. Палатка.
Задача С. Чемпионат по грибному спорту.
Задача D. Виннимобиль.
Задача Е. Схемы рифмовки.
Задача F. Шахтеры.
Задача G. Подарок Пятачку.
Задача Н. Игральная кость.
Задача I. Пятизвездочная задача.
Задача J. Прочные замощения.
Задача К. Гамильтонов трубопровод.
Задача L. Шестиугольник и ромбические домино.
Задача М. Симпатичные узоры 2.
День четвертый. День Киевского Политехнического Института.
Об авторах.
Теоретический материал. Вероятностные структуры данных.
Задачи и разборы.
Задача А. Инопланетяне.
Задача В. Конфеты.
Задача С. Раскраска.
Задача D. Сортировка вагонов.
Задача Е. Максимальный поток.
Задача F. Митохондриальная ДНК.
Задача G. Кратные запросы.
Задача Н. Ориентирование.
Задача I. Гонки.
Задача J. TR3N.
Задача К. Хамелеоны.
Задача L. Площадь кольца.
День пятый. Контест Копелиовича Сергея Владимировича.
Об авторе.
Теоретический материал. Перебор с отсечениями.
Задачи и разборы.
Задача А. Карточки.
Задача В. Функция.
Задача С. Пути на доске.
Задача D. Тестирование шаффл-машин.
Задача Е. Белка и бамбук.
Задача F. Снеговики.
Задача G. Вершинное покрытие.
Задача Н. Праздничные дни.
Задача I. Самый длинный путь.
Задача J. Сумма не без разнообразия.
Задача К. Валидатор к игре в тетрис.
Задача L. Возьми себе за правило — летай всегда GraphAero!.
Задача М. Тест к задаче про Клики.
Задача N. Задача про Клики.
Задача О. Connect and Disconnect.
Задача Р. Кривые зеркала.
Задача Q. Сортировка вручную.
Задача R. СНМ.
День шестой. Контест Виталия Неспирного и Антона Лунёва.
Об авторах.
Теоретический материал. Близость точек на плоскости. Диаграмма Вороного.
Задачи и разборы.
Задача А. Количество линий.
Задача В. Восстановление количества очков.
Задача С. Как побить все рекорды.
Задача D. Секретный уровень.
Задача Е. Поля сражений.
Задача F. Взлом таблицы рекордов.
Задача G. Горная гряда.
Задача Н. Постройка склада.
Задача I. Сила героя.
Задача J. Караваны.
Задача К. Кто ходит в гости по утрам.
Задача L. Принц или самозванец.
Задача М. Что? Где? Когда?.
Задача N. Укладка плит.
Задача О. Прохождение коридора.
Задача Р. Игра.
Задача Q. Гамильтонов цикл.
Задача R. Очень дружная группа.
Задача S. Деревья с нечетным числом независимых множеств.
Задача Т. Максимальная степень простого.
Задача U. Минимальная степень простого.
День седьмой. Контест Эльдара Богданова и Ивана Метельского.
Об авторах.
Теоретический материал. Ориентированные графы. Задача 2-SAT.
Задачи и разборы.
Задача A. Anniversary.
Задача G. Король.
Задача Н. Каток.
Задача I. Предок.
Задача J. Неизбежность.
Задача К. Мосты.
Задача L. Цветные волшебники.
Задача М. Точки сочленения.
Задача N. Почтальон.
Задача О. Конденсация графа.
Задача Р. Топологическая сортировка.



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

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


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




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