Главная страница
Навигация по странице:

  • 5. Алгоритмы вычислительной геометрии

  • Алгоритмы вычислительной геометрии 261

  • 262 5. Алгоритмы вычислительной геометрии

  • 5. Алгоритмы вычислительной геометрии 263

  • 6. Избранные олимпиадные задачи по программированию

  • Избранные задачи по программированию

  • Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница18 из 26
    1   ...   14   15   16   17   18   19   20   21   ...   26
    5. Алгоритмы вычислительной геометрии 259
    Begin
    ввод данных. *}
    Write ('Ответ >
    If
    And
    (OnY, ObY)
    Then
    ' ,Abs ( (ObX.L-ObX.R) *
    (ObY.L-ObY.R)) :0:6)
    Else
    нет. *);
    End.
    5.7. Задачи
    Дана прямоугольная призма, основанием которой являет- ся выпуклый
    Необходимо разделить её
    на К частей равного объема. Разрешается проводить прямые вертикальные разрезы от одной границы призмы до другой. Различные разрезы могут иметь общие точки лишь в своих концевых вершинах.
    Написать программу построения требуемых разрезов.
    Указание. В основании призмы лежит выпуклый многоугольник,
    в этом вся суть решения, его опре- деленная простота. Задача решает- ся на уровне многоугольника, ле- жащего в основании. Через его вершину всегда можно провести отрезок прямой и «отсечь» пло- щадь, меньшую площади исходно- го многоугольника, причем оба по- лучившихся многоугольника будут выпуклыми. Отсюда следует, что многоугольник можно «раз- резать» на куски площади частей>, про- ведя все разрезы через одну вершину. Число прямых равно числу частей минус 1. Пусть мы нашли площадь треугольника она меньше площади отрезаемого куска. Добавляем к ней площадь треугольника
    Если по-прежнему пло- щадь куска не превышена, то продолжаем процесс. В общем,
    мы рано или поздно придем к случаю, когда потребуется отсечь от какого-то треугольника треугольник площадью
    (площадь второго получаемого треугольника (S'') также известна), при- чем одна точка разреза — вершина, а вторая «плавает» по про- тивоположной стороне. Нам необходимо вычислить координа- ты точки М. Высоты треугольников равны, поэтому
    S'/S'
    После этого следует изменить выпуклый

    260
    5. Алгоритмы вычислительной геометрии
    многоугольник («выкинуть» из него те точки, которые мы включили в отрезанный кусок). Легче это сделать, если начать процесс отрезания затем
    , а не и т. д. В
    этом случае не придется сдвигать элементы массива А.
    2. Дан простой многоугольник со сторонами, параллельны- ми осям координат. Три последовательно соединенных верши- ны многоугольника не лежат на одной прямой. Требуется опре- делить, существует ли такая точка внутри многоугольника, из которой видимы все внутренние точки многоугольника.
    Число вершин многоугольника N
    и их координаты заданы в порядке обхода по часовой стрелке. Все координа- ты — целые. Ответом является сообщение Yes или No.
    Воспользуемся следующим алго- ритмом: все вертикальные отрезки по- делим на две группы — восходящие и нисходящие. Аналогично и для гори- зонтальных отрезков (идущих вправо и влево). Среди первых выберем отре- зок с максимальной абсциссой (max),
    среди второй группы — с минималь- ной абсциссой (min). Назовем условие выполнимым, если max Иско- мая точка существует в том случае, если это условие выполня- ется как по оси X, так и по оси У. Объяснение этому факту до- статочно простое. Искомая точка находится в заштрихованной полуплоскости для каждого рассматриваемого отрезка. Если условие не выполняется, то полуплоскости не пересекаются.
    Приведите возможный текст решения.
    3. Отражение агрессии. Для своевременного отражения воз- можной воздушной агрессии на город необходимо обнаружи- вать средства воздушного нападения противника в момент под- лета к границе «опасной зоны» — на расстояние R от центра города, который мы примем за начало координат. Имеются N
    комплексов ПВО, расположенных в точках с координатами
    ...,
    Для каждого комплекса i (l изве- стен радиус его действия
    Напишите программу, которая:
    • определяет, надежно ли защищен город от нападения,
    т. е. верно ли, что обнаружение происходит при подлете к границе «опасной зоны» с любого направления;
    • в случае отрицательного ответа на первый пункт опреде- ляет диапазоны «опасных» направлений, т. е. таких на- правлений, с которых при подлете обнаружение не проис-

    Алгоритмы вычислительной геометрии 261
    ходит. Направление задается углом (от 0° до 360°), на который нужно повернуть луч Ох против часовой стрел- ки, чтобы он совпал с этим направлением. Например, на- правление на точку соответствует числу 0, а на точ- ку
    — числу 90.
    В первой строке входного файла содержится натуральное число и вещественное число R. В последующих строках записано N троек вещественных чисел каж- дая из которых задает координаты и радиус действия одного из комплексов ПВО. Числа разделяются пробелами и/или симво- лами перевода строки. Все вещественные числа по модулю не превосходят 1000.
    Первая строка выходного файла должна содержать ответ Yes/No. В случае отрицате- льного ответа вторая строка должна содер- жать количество диапазонов «опасных» на- правлений (К), а каждая из последующих строк — начало и конец очередного из диа- пазонов. Диапазоны должны быть перечис- лены в порядке обхода против часовой стрелки.
    Указание. Рассмотрим следующий рису- нок. Лучше вначале проверить, не защищает ли какая-нибудь одна ПВО весь город. Если да, то ответ очевиден, иначе опреде- лим все точки пересечений зон ПВО и зоны города. Точки типа
    2 и 3 исключаем, а точки типа 1, 2, 4, 5 сортируем по значению полярного угла. Все эти точки являются защищенными, а зна- чит, те интервалы, которые они (точки) разделяют, не объеди- няются. После этого остается проверить интервалы на принад- лежность какой-нибудь зоне ПВО.
    4. На плоскости заданы треугольник и отрезок. Определить их взаимное расположение.
    5. На плоскости заданы два треугольника (координатами своих вершин).
    • Определить взаимное расположение треугольников;
    • найти замкнутую ломаную линию, ограничивающую об- ласть, общую для обоих треугольников (если она есть).
    6. На плоскости заданы два треугольника. Используя пере- мещения и повороты, определить, можно ли один из треуголь- ников вложить в другой.
    7. Даны два прямоугольника со сторонами, параллельными осям координат. Определить их взаимное расположение. Для случая, когда прямоугольники пересекаются, вычислить:
    3500

    262 5. Алгоритмы вычислительной геометрии
    • замкнутую ломаную, ограничивающую область, объеди- няющую оба прямоугольника;
    • замкнутую ломаную, ограничивающую область, общую для обоих прямоугольников;
    • площадь области, общей для обоих прямоугольников.
    Снять ограничение о параллельности сторон прямоугольни- ков осям координат. Исследовать задачу.
    8. На плоскости координатами своих вершин заданы два прямоугольника. Путем их перемещений и поворотов устано- вить, можно ли один из прямоугольников вложить в другой.
    9. На плоскости задано точек. Найти две наиболее удален- ные друг от друга точки (диаметр множества). Утверждение.
    Диаметр множества равен диаметру его выпуклой оболочки.
    10. На плоскости задано N точек. Требуется разбить их на групп
    ...,
    таким образом, чтобы максимальный из диа- метров групп был минимален.
    11. На плоскости заданы точек. Найти две из них, рассто- яние между которыми наименьшее.
    12. На плоскости заданы N точек. Найти ближайшего «сосе- да» для каждой точки.
    13. Из заданного множества точек на плоскости выбрать две точки так, чтобы количество точек, лежащих по сторонам от прямой, проходящей через эти две точки, различалось наи- меньшим образом.
    14. Определить радиус и центр окружности, на которой ле- жит наибольшее число точек заданного на плоскости множест- ва точек.
    15. На плоскости задано множество N произвольным обра- зом пересекающихся отрезков прямых линий. Перечислить множество всех треугольников, образованных указанными от- резками.
    16. На плоскости заданы точек. Найти минимальное ко- личество прямых, на которых можно разместить все точки.
    17. Евклидово минимальное остовное дерево (каркас). На плоскости заданы N точек. Построить дерево, вершинами кото- рого являются все заданные точки, и суммарная длина всех ре- бер минимальна.
    18. Триангуляция. На плоскости заданы точек. Соединить их непересекающимися отрезками таким образом, чтобы каж- дая область внутри выпуклой оболочки этого множества точек являлась треугольником.
    19. Минимальное евклидово паросочетание. На плоскости задано 2*N точек. Объединить их в пары, соединив отрезками так, чтобы сумма длин отрезков была минимальна.

    5. Алгоритмы вычислительной геометрии
    263
    Примечание
    Известен алгоритм со сложностью
    20. Наименьшая охватывающая окружность. На плоскости заданы N точек. Найти наименьшую окружность (по значению радиуса), охватывающую все заданные точки.
    Примечание
    Эта задача известна под названием «минимаксная задача о разме- щении центра обслуживания». Требуется найти точку
    (центр окружности), для которой наибольшее из расстояний до то- чек заданного множества минимально. Точка определяется кри- терием
    21. Наибольшая «пустая» окруж- ность. На плоскости заданы N точек.
    Найти наибольшую окружность, не содержащую внутри ни одной точки этого множества. Центр окружности должен находиться внутри выпуклой оболочки множества точек.
    Примечание
    Известно, что как задачу о наименьшей охватывающей окружно- сти, так и задачу о наибольшей «пустой» окружности можно ре- шить за время, пропорциональное O(N*LogN).
    22. Даны два выпуклых многоугольника и
    с N и М
    вершинами соответственно. Построить их пересечение.
    Указание. Пересечением выпуклых многоугольников с N
    М вершинами является выпуклый многоугольник, имеющий не более N+M вершин.
    23. Даны два выпуклых многоугольника и
    с N и М
    вершинами. Найти выпуклую оболочку их объединения.
    Указание. Метод обработки. Находим некоторую внутрен- нюю точку t многоугольника
    (центр масс трех любых вершин
    Определяем, является ли точ- ка t внутренней точкой многоуго- льника
    (за время, пропорциона- льное
    Если точка t
    является внутренней точкой то вершины как так и упорядо- чены в соответствии со значением полярного угла относительно точки t. За время, пропорциональное получаем упорядо- ченный список вершин как так и путем слияния списков вершин этих многоугольников. К полученному списку точек применяем метод обхода Грэхема. Если точка t не является

    264
    5. Алгоритмы вычислительной геометрии
    внутренней точкой то многоугольник лежит в клине с углом, меньшим или равным
    Этот клин определяем двумя вершинами и и v многоугольника которые находим за один обход вершин многоугольника
    Вершины и и v разбивают границу на две цепочки вершин, монотонные относительно изменения полярного угла с началом в точке t. При движении по одной цепочке угол увеличивается, при движении по дру- гой — уменьшается. Одну из этих цепочек удаляем (ее точки являются внутренними относительно строящейся оболочки).
    Другая цепочка и граница являются упорядоченными спис- ками. Соединяем их в один список вершин, упорядоченный по полярному углу относительно точки t, и выполняем обход.
    24. Определить принадлеж- ность точки р выпуклому iV-угольнику Q.
    Указание. Методом двоично- го поиска находим «клин».
    Точка р лежит между лучами,
    определяемыми и
    тогда и только тогда, когда угол положительный, а угол отрицательный. Сравниваем р с единственным ребром.
    Точка р внутренняя тогда и только тогда, когда угол
    25. Разработать функции:
    • построения окружности по трем точкам;
    • нахождения пересечения прямой и окружности;
    • нахождения точек пересечения двух окружностей.
    26. Построить выпуклую оболочку для множества точек на плоскости без использования операций с вещественным типом данных.
    Указание [2]. Строим выпуклую оболочку в порядке обхода против часовой стрелки. Находим самую правую нижнюю точ- ку
    Она принадлежит выпуклой оболочке. Следующей является точка для которой угол между осью X и векто- ром
    -
    минимален. Если таких точек несколько, то выбирается точка, расстояние до которой максимально. Суть идеи заключается в том, чтобы угол не вычислять, а вычислять знак выражения
    -
    где

    очередная точка, вошедшая в выпуклую оболочку,

    следующая точка выпуклой оболочки, а (х,у) — координаты любой точки, не вошедшей в выпуклую оболочку. Выражение отрицательно, и это является «ключом» решения задачи.

    5. Алгоритмы вычислительной геометрии 265 27. На плоскости заданы N точек. Построить замкнутую ло- маную без самопересечений и самокасаний, координатами ко- торой должны стать все заданные точки.
    Указание. Построить часть выпуклой оболочки между самой левой и самой правой (по координате X) точками. Оставшиеся точки отсортировать по координате X и затем последовательно соединить отрезками.

    6. Избранные олимпиадные
    задачи по программированию
    1. Дано целое неотрицательное число N
    запи- си N в двоичной системе счисления получается последователь- ность из 1 и 0. Например, при получаем
    =
    т. е. в двоичной системе
    10011 11001
    вправо получаются другие числа. Найти максима-
    00111 10011
    число запишется как
    При циклическом сдви- ге вправо получаются другие числа. Найти максима- льное среди этих чисел. Так, для числа 19 список по- следовательностей показан на рисунке, а результатом является число
    = 28.
    Указание. Находим старший значащий разряд в двоичном представлении числа N, ибо бессмысленно, напри- мер, в числе 000000001010 выполнять лишние сдвиги, соответ- ствующие первым нулям. После того, как значение числа сдви- гов найдено, последовательно изменяем значение N и находим его максимум. Задача становится более интересной, если снять ограничение
    N
    Как минимум не избежать длин- ной арифметики и моделирования выполнения операций сдви- га на один двоичный разряд.
    Procedure Solve;
    i, j: Integer;
    Begin
    i:=0;
    While ((N shr i)>l) Do
    (i) ;{ *Определяем место
    первой единицы справа в двоичном
    представлении числа N. *}
    j
    Число сдвигов *}
    While j<>0 Do Begin
    N:=(N shr 1) + (N And 1)
    i ; { *Сдвигаем вправо
    на один разряд и приписываем
    единицу. *}
    If N>Res Then
    Dec(j) ;
    End;
    End;
    2.
    на Луне». Время от времени пролетающие вблизи нашего спутника Луны астероиды захватываются ее

    6. Избранные олимпиадные задачи по программированию
    267
    гравитационным полем и, будучи ничем не задерживаемы, вре- заются с огромной скоростью в лунную поверхность, оставляя в память о себе порядочных размеров кратеры приблизительно круглой формы.
    Требуется найти максимально длинную цепочку вложенных друг в друга кратеров.
    Формат входных данных. Первая строка входного файла со- держит целое число N — количество кратеров, отмеченных на карте
    Следующие N строк содержат описания кра- теров с номерами от 1 до N. Описание каждого кратера занима- ет отдельную строку и состоит из трех целых чисел, принадле- жащих диапазону [—32768, 32767] и разделенных пробелами.
    Первые два числа представляют собой декартовы координаты его центра, а третье — радиус. Все кратеры различны.
    Формат выходных данных. Первая строка выходного файла должна содер- жать длину искомой цепочки кратеров,
    вторая — номера кратеров из этой цепоч- ки, начиная с меньшего кратера и кончая самым большим. Номера кратеров должны быть разделены пробелами. Если сущест- вует несколько длиннейших цепочек, нуж- но вывести любую из них.
    Указание. Ответить на вопрос о принадлежности одного кра- тера другому достаточно просто. Пусть координаты центров кратеров и их радиусы хранятся в массивах (Const
    Var
    Ay,
    Of
    В каком случае кратер с номером i вложен в кратер с номером у? Если точки с координатами (Ax[i]+Ar[i], Ay[i]), (Ax[i]-Ar[i], Ay[i]),
    (Ax[i], Ay[i]+Ar[i]), (Ax[i], Ay[i]-Ar[i]) принадлежат крате- ру с номером то и весь кратер с номером i находится в крате- ре с номером Точка находится внутри окружности (кратера) в том случае, если расстояние между точкой и центром окружно- сти меньше радиуса.
    Рассмотрим еще один пример. Пусть есть расположение кратеров, показанное на рисунке,
    и в массивах Sc, Ls:Array[l..N] Of Integer; ка- (
    ®)
    ким-то образом оказались следующие данные:
    Sc — (3, 0, 1, 0, 1, 2) и Ls — (6, 0, 2, 0, 4, 5).
    Найти максимальный элемент в Sc
    и
    его номер несложно. Если вывести значение найденного максимума и вызвать процедуру SayRes(k)нашем случае будет SayRes(l))
    Пример.
    4 0 0 30
    -15 15 20 15 10 5 10 10 10
    d.out
    3 3 4 1

    Избранные
    задачи по программированию
    Procedure SayRes
    Integer);
    Begin
    If Ls[k]<>0 Then
    Write (k, '
    End;
    то получим:
    4 4 5 6 1, что и является ответом задачи. Итак, осталось понять,
    как формировать значения элементов массивов Sc и Ls.
    3. На клеточном поле задано N точек (в узлах клеточного поля). Требуется найти точку, до кото- рой суммарное расстояние от заданного множества точек минимально. Расстояние считается при про- хождении по границам клеток.
    Формат входных данных. Первая строка вход- ного файла содержит число N — количество точек
    Каждая из последующих N строк содержит коорди- наты точки — два целых числа из диапазона [-32767, 32767],
    разделенных пробелом.
    Формат выходных данных. Ваша программа должна вывес- ти в выходной файл координаты точки — два целых числа, за- писанных через пробел.
    Указание. Зачем нам плоскость? Почему задачу нельзя ре- шить отдельно для каждого измерения? Результат решения на плоскости — это результат решения на двух прямых, т. е. на- шли точку на X, нашли точку на Y, тем самым получили коор- динаты точки на плоскости. Решаем задачу на прямой линии.
    Пусть не N точек, а две. Очевидно, что точку следует размещать в том месте, где находится одна из точек. А если три точки? На- пример, (1, 5, 1000). В этом случае ответом является 5.
    4. «Печать буклета». При печати документа обычно первая страница печатается первой, вторая — второй, третья — третьей и так далее до конца. Но иногда, при созда-
    Пример.
    4 0
    0 1
    2 01 0
    0 1
    2
    нии буклета, порядок печати должен быть
    1   ...   14   15   16   17   18   19   20   21   ...   26


    написать администратору сайта