Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
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 Приведите возможный текст решения. 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 нии буклета, порядок печати должен быть |