    Г Л А В А 2 

    НЕСКОЛЬКО ПРИМЕРОВ ПРОГРАММ 

    9. Проект «Выпуклая оболочка последовательно поступающих точек плоскости» 
Формулировка задачи. Пусть требуется создать исполнителя для вычисления 
некоторых геометрических характеристик (наприт мер, периметра и площади) 
выпуклой оболочки последовательно по-ступающих точек плоскости. 
    Напомним, что выпуклой оболочкой conv(M) множества М точек плоскости 
называется минимальное выпуклое множество, содержащее все заданные точки. Если 
представить себе точки конечного множества в виде вбитых в доску гвоздей, то 
выпуклая оболочка — это многоугольник, форму которого при-нимает натянутое на 
гвозди резшю-вое кольцо (рис. 9.1). 
    Слова «последовательно посту» дающих» означают, что точки множества не 
заданы все сразу, а поступают друг за другом, причем в любой момент времени 
исполнитель должен уметь ответить на вопрос о периметре или площади выпуклой 
оболочки уже поступивших точек. Таким образом, требуется создать исполнителя 
«Выпуклая оболочка» со следующей системой предписаний: 
    1. начать работу 
    2. добавить точку <вх : точка R2> 
    3. периметр	: число 
    4. площадь	: число 
    5. кончить работу где тип: 
    точка R2 = запись (X, Y: число) 
    Никакого базового исполнителя в условии задачи не задано, (Г. е. при 
реализации Выпуклой оболочки можно пользоваться лишь возможностями 
Универсального Выполнителя. 

    Ряс.   9.1.  Выпуклая  оболочка множества точек плоскости 


    И. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА» 137 

    Естественно, возможны разные стратегии решения этой задачи, например: 
    1) хранить все поступающие точки — это позволяет мгновенно обрабатывать 
добавление новой точки, но требует существенных усилий при вычислении 
периметра и площади; 
    2) хранить только вершины выпуклой оболочки уже поступивших точек 
(очевидно, что этого достаточно для вычисления выпуклой оболочки при 
добавлении новой точки) — это сокращает объем хранимой информации и ускоряет 
вычисление периметра и площади, но усложняет добавление новой точки; 
    3) хранить не только выпуклую оболочку уже поступивших точек, но и ее 
периметр и площадь, т. е. вообще все действия производить при добавлении новой 
точки, а по предписаниям «периметр» и «площадь» лишь выдавать готовые значения. 
    Выбор той или иной стратегии решения должен определяться спецификой 
задачи: если точки поступают часто и их надо обрабатывать быстро, а запросы на 
периметр и площадь редки, то можно выбрать первую стратегию; если, наоборот, 
точки поступают редко и время их обработки не очень важно, а запросы про 
периметр и площадь требуют максимально быстрого ответа, то лучше избрать 
третий вариант. Мы будем считать, что условия задачи требуют мгновенной выдачи 
периметра и площади выпуклой оболочки уже поступивших точек, и будем 
придерживаться третьей стратегии. 
    Основные идеи. Фактически в этой задаче мы имеем дело с функцией на 
пространстве последовательностей точек плоскости. Значением функции является 
выпуклая оболочка точек последовательности, а также периметр и площадь этой 
оболочки. Схема индуктивного вычисления функции в данном случае означает, что 
при добавлении новой точки х мы не вычисляем заново новую выпуклую оболочку 
[(ш*х), а модифицируем старую оболочку f(w), т. е. выражаем f(co*x) через f(o) 
и х. 
    Отложим пока вопросы про периметр и площадь и посмотрим, как меняется 
выпуклая оболочка при добавлении новой точки.1 Ясно, что если новая точка 
оказалась внутри или на границе старой выпуклой оболочки, то оболочка не 
меняется. Если же новая точка оказалась вне старой оболочки, то оболочка 
меняется так, как изображено на рис. 9.2. Если в новой точке расположить 
лампочку, то она осветит удаляемые ребра старой оболочки; поэтому будем 
называть эти ребра освещенными из новой точки или просто освещенными. Алгоритм 
модификации выпуклой оболочки можно описать так: 
    II) удалить освещенные   ребра, 2) концы оставшейся ломаной . . соединить 
двумя новыми ребрами с новой точкой

    138 ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ  ПРОГРАММ 

    Мы, впрочем, описали только общий случай. Если новая точка лежит   на   
продолжении   одного   из   ребер,   то   оболочка   должна новая точк* Т 
    Старая оеолочка	иовая оболочка Рис. 9.2 измениться, так, как показано на 
рас. 9.3. Поэтому ребро, на продолжении которого лежит точка, мы также будем 
считать освещенным, 

    новая точка 
    / \ 
    I \ 
    О 
    старая оволочка	новая оволочка 

    Рис. 9.3 

    Остановимся пока на этом уровне детальности и посмотрим, начиная с какой 
оболочки работает алгоритм (*). Поскольку в нем фигурируют «оставшаяся 
ломаная» и ее концы, то алгоритм работает, лишь начиная с невырожденного 
многоугольника. Следовательно, пустая (нет точек), нульмерная (одна точка) и 
одномерная (отрезок) выпуклые оболочки — это особые случаи, которые должны 
обрабатываться отдельно. 
    По сути дела, это первое (после выбора стратегии) волевое решение —мы 
разбили нашу задачу на две: перечисленные выше особые случаи и общий случай, 
когда выпуклая оболочка двумерна. Поэтому, действуя в соответствии с 
технологией «сверху вниз», примем решение, что для обработки общего случая у 
пас будет спе-циальный исполнитель «Многоугольник», и по пробуем реализовать 
исполнителя «Выпуклая оболочка» на его базе. (Заметим, что эти решения 
действительно являются волевыми —мы могли бы вместо них пытаться заменить (*) 
на алгоритм, который работает, начиная с отрезка или даже с одной точки, но не 
стали этого делать.) 
    Первый шаг декбмпозиции. Итак, реализуем исполнителя «Выпуклая оболочка» 
на базе исполнителя «Многоугольник», который должен производить все действия с 
невырожденной (двумерной) 

    Э. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА»' 139 

    выпуклой оболочкой. Начнем с предписания «добавить точку». Поскольку нам 
надо как-то различать, с каким случаем *ш имеем дело, то введем глобальную 
переменную которая будет содержать число «углов» (вершин) в выпуклой оболочке. 
Тогда программу «добавить точку» можно записать в виде; 
    !       число углов: перечисление (нуль, один, два, много) 
    программа добавить точку (вх : Т : точка R2) 
    . дано        : |поступила новая точка Т 
    . получить: [новая оболочка =conv (старая оболочка, Т) 
    . выбор	„ 
    . . при число углов = нуль =»• обработка нульугольника (вх:Т) . . при 
число углов=один ^обработка одноуголышка (вх:Т) . . при число углов = два 
•=>-обработка двуугольника (вх : Т) . . при число углов = много =Ф- обработка 
многоугольника (вх : Т) . конец выбора ионец программы 
    где «обработка нульугольника», «обработка одноугольника» и др. -^ это 
подпрограммы (локальные предписания "исполнителя «Выпуклая оболочка»). Нам, 
впрочем, понадобится где-то хранить выпуклую оболочку уже поступивших точек. 
Если она не вырождена, мы будем хранить ее в исполнителе «Многоугольник», а 
для особых случаев заведем глобальные объекты А и 
    В типа «точка R2», в которых будем хранить точку (в А) нульмерной оболочки 
или концы отрезка (А, В) одномерной. 
    Таким образом, обработка нульугольника состоит просто в запоминании 
поступившей точки и получении одноугольника; программа обработка нульугольника 
(вх : Т : точка R2) . дано        :    число углов = нуль | старая оболочка 
пуста . получить: (новая оболочка= Т 
    . А := Т         
    . число углов := один 
    конец программы 
    При обработке 'одноугольника новая точка может попасть в старую выпуклую 
оболочку (совпасть со старой точкой) — в этом случае оболочка не меняется: 
программа обработка одноугольника (вх : Т : точка R2) 
    • дано        :   число углов = один [старая оболочка — точка А 
    . получить: [новая оболочка = conv (А, Т) 

    140	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 


    .   если Т = А то ничего не .делать иначе 
    .   .    В:=Т 
    .   .    число углов := два 
    .    конец если 
    конец программы 

    При обработке двуугольника (отрезка) возможны уже три раз» иых случая: 
новая точка принадлежит старому отрезку (оболочка не меняется); новая точка 
вне отрезка, но на одной прямой с ним (отрезок меняется, но остается 
отрезком); новая точка находится в общем положении с концами отрезка (оболочка 
становится тре«. угольником). При анализе этих случаевнам придется узнавать, 
находятся ли точки А, В и Т на одной прямой, находится ли точка Т между А и В 
и т. п. Для выполнения таких элементарных дей« ствий на плоскости мы введем 
исполнителя «Планиметр> и будем реализовывать Выпуклую оболочку на базе 
исполнителей «Многоугольник» и «Планиметр». 
    Не выписывая дальнейших рассуждений, приведем полную реа« лизацию 
исполнителя «Выпуклая оболочка»; 
    исполнитель Выпуклая оболочка . СП: 
    1. начать работу 
    2. добавить точку {вх: точка R2) 
    — обработка нульуголышка (вх: точка R2) 
    — обработка одноугольника (вх:точка R2) .	— обработка двуугольника 
(вх:точка R2) .            —обработка многоугольника (вх:точка R2) 
    3. периметр 
    4. площадь 
    5. кончить работу 
    tчисло ;число 
    . типы: 
    точка R2 = запись (X,Y:число) 
    . объекты: 
    число углов: перечисление (нуль,один,два,много) А,В	: точка R2 
    . идеи реализации: 
    .	будем хранить выпуклую оболочку поступивших точек и при поступлении 
новоХ точки модифицировать ее и ее характеристики (периметр, площадь) 


    9. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА» 


    . используемые исполнители: 
    Многоугольник (М) и Планиметр (П) конец описаний | — — ——— ———————————— 
    программа начать работу'=*= число углов.установить в нуль 
    программа добавить точку (вх: Т: точка R2) 
    . дано        :   [поступила новая точка Т 
    . получить: |новая оболочка = conv (старая оболочка,!) 
    . выбор 
    . . при число углов = нуль =*• обработка нульугольника {вх : Т) . . при 
число углов = один *$• обработка одноугольника (вх: Т) . . при число углов = 
два =* обработка двуугольника» {вх: Т) . . при число углов = много <=Ф- 
обработка многоугольника {вх: Т) . конец выбора конец программы 
    программа обработка нульугольника {вх: Т : точка R2) . дано        :   
число углов = нуль | старая оболочка пуста . получить: | новая оболочка = Т 
    . А:=Т	~-          ' . число углов := один конец программы 
    программа обработка одноугольника {вх : Т : точка R2) 
    . дано       :   число углов = один | старая оболочка — точка А 
    . получить: | новая оболочка = conv (А,Т) 
    .   если Т = А то ничего не делать иначе 
    .    .     В:=Т 
    .   .    число углов := два 
    .    конец если 
    конец программы 
    программа обработка двуугольника {вх: Т: точка R2) 
    . дано       : число углов = два (старая оболочка = отрезок [А,В] 
    . получить: | новая оболочка = conv ([А,В],Т) 
    . выбор 
    . , при П.точки (А,В,Т) не на одной прямой =*• 
    . .	М.начать работу {вх: А.В.Т) 
    . .     .	число углов := много 
    
    , , при П.точка (Т) внутри отрезка (А, В} =*• ничего не делать 

    142 .ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    . . при П.точка (В) внутри отрезка (A,T)=s-B:=T . . при П.точка (А) внутри 
отрезка <Т,В}=*-А:=Т . конец выбора конец программы 
    программа обработка многоугольника ^вх: Т) = = М.обработать 
    <вх: Т) 
    программа периметр; число , дано        : . получить: 


    9. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА» 143 


    . выбор 
    . .   при число углов = . .   при число углов; . .   иначе . конец выбора 
конец программы 

    -. много»*- ответ :=М.периметр многоугольника = два   ^ответ:= =>-ответ: = 0 
    программа площадь: число . дано        : . получить: 
    .    если число углов =?ь много то ответ := 0.0 аиазе .     .     ответ := 
М.площадь многоугольника 
    конец если конец программы программа кончить работу .   дано        : .   получить: 
    если число углов = много то М.кончить работу конец если конец программы 
конец   исполнителя ] 

    Заметьте, что мы начинаем работу с исполнителем «Многоугольник» только в 
тот момент, когда выпуклая оболочка становится двумерной. Возможен случай, 
когда этого не происходит. Поэтому о программе «кончить работу» мы кончаем 
работу с исполнителем «Многоугольник» только в том случае, если оболочка 
является двумерной. 
    Второй шаг декомпозиции. Наша задача сейчас — реализовать исполнителя 
«Многоугольник», система предписаний которого выглядит так: 
    1. начать работу <BXS А, В, С: TO4KaR2) 
    2. обработать <вх; Т: точка R2> 
    3. периметр многоугольника	: число 
    4. площадь многоугольника	: число 
    5. кончить работу 
    Поскольку мы приняли решение все действия, включая вычис* ление периметра 
и площади выпуклой оболочки, производить при добавлении новой точки, то у нас 
будут глобальные объекты периметр, площадь: число значения которых будут 
модифицироваться при поступлении новой точки. Программы «периметр 
многоугольника» и «площадь много-i угольника» при этом становятся 
тривиальными: программа периметр многоугольника: число = = периметр программа 
площадь многоугольника: число == площадь 
    Напомним, что такая запись эквивалентна следующей: 
    программа  площадь многоугольника: число 
    .  дано        : 
    .   получить:	, 
    ответ := площадь конец программы 
    Основное, что нам осталось, — это реализовать предписание «обработать», т. е. модифицировать выпуклую оболочку, а также ее периметр и площадь при 
поступлении новой точки. Прежде всего заметим, что понятие освещенности в [(*) 
было определено неформально и при этом использовалось расположение точки 
относительно всего многоугольника. Желательно было бы, чтобы освещенность или 
нсосвещсшюсть ребра определялась только по точке и ребру. Это можно сделать 
для ориентированных ребер (ориентированного многоугольника) следующим образом: 
рассмотрим ориентированное ребро АВ, новую точку Т и ориентированную площадь 
треугольника АВТ (рис. 9.4): 5(ДАВТ)=г i=((A.X — T.X)*(B.Y — 
T.Y)-(A.Y—T.Y)*(B.X — T.X))«0.5 (ориенти-рованная площадь треугольника 
считается как половина площади параллелограмма, натянутого на векторы ТА и ТВ). 
    Легко видеть (рис. 9.5), что если многоугольник ориентирован «против 
часовой стрелки», то ребро АВ освещено из Т тогда и .только тогда, когда 
    s (ДАВТ) (0    или    (s (ДАВТ) = 0 и точка Т вне отрезка АВ}. 

    144	ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    Заметим также, что при таком формальном определении понятия освещенности 
никакое ребро многоугольника не освещено ни из одной точки внутри или на 
границе многоугольника. 

    9. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА»    145 

    В)    5<0 
    Рис.   9.5 
    Далее надо понять, как хранить многоугольник (выпуклую оболочку). Мы 
примем решения 
    1) хранить линейно упорядоченную последовательность вершин многоугольника 
(ориентация против часовой стрелки); 
    2) сами эти вершины хранить в деке Д элементов типа «точка R2» (рис. 9.6) 
*). Ребро а, соединяющее конец дека с началом, назовем текущим. Поскольку в 
деке в каждый момент доступны только два элемента — начало и конец, то и 
работать можно только 

    0 
    00© 
    6) 

    Рис.   9.6.    а)    многоугольник,    б)    состояние   дека    (указаны  
 номера   точев плоскости) 

    с текущим ребром многоугольника. Текущее ребро многоугольника, впрочем, 
легко сменить: если переместить один элемент из начала дека в конец, то 
многоугольник нь изменится, а текущим ребром станет ребро b (следующее за а в 
порядке против часовой стрелки), 
    *) Хотя выбор дека и кажется произвольным, это не вполне верно. Выбор 
конкретной структуры для хранения вершин многоугольника определяется теми 
операциями, которые будут производиться над вершинами при обработке новоА 
точки. Таким образом, нам следовало попытаться как-нибудь (вчерне) написать 
программу «обработать», прикинуть, какие операции над вершинами нужны, ч лишь 
после этого выбирать подходящую структуру и реализовывать программу 
«обработать» начисто. Так оно и было на самом деле. Здесь, однако, мы 
опи"сываем лишь «чистовой» вариант, что и приводит к кажущейся произвольности 
решения 2. 
    Если переместить из  начала дека в конец еще один элемент, то текущим 
станет ребро с и т. д. 
    Таким образом, модификация выпуклой оболочки при поступлении новой точки 
достаточно формализована, и мы можем начать писать соответствующую программу. 
Осталось еще понять, как должны модифицироваться периметр и площадь. 
Желательно было бы описать эти изменения в терминах элементарных операций над 
ребрами — что надо делать с периметром и площадью при удалении одного отдельно 
взятого освещенного ребра И что при добавлении новых ребер. В данном случае 
это достаточно просто: периметр надо при удалении ребра уменьшать на длину 
ребра, а при добавлении увеличивать; площадь же надо увеличивать па величину 
площади треугольника AT В при удалении каждого освещенного ребра АВ, а при 
добавлении новых ребер ничего делать не надо (рис. 9.7). Заштрихованная на 
рис. 9.7 площадь состоит из площадей треугольников АВТ цля каждого освещенного 
ребра АВ * (на |<нс. 9.7 таких ребер три). Далее нам понадобится еще и число 
ребер выпуклой оболочки, поэтому кроме периметра и площади будем 
модифицировать также и число ребер. Подпрограмму, учитывающую удаление 
освещенного ребра, можно записать так: 
    программа учесть удаление ребра (вх: А,В) (вх: Т:  точка R2) 
    ,   дано        :   А,В: точка R2 [удаляемое ребро 
    ,	и ребро (Л, И) освещено из (Т) 
    ,   получить: | число ребер, периметр и площадь соответствующим. 
    ,	| образом изменены 

    Рис. 9.7 

    .    число ребер.уменьшить на 1	' ,     периметр.уменьшить на П.К(А,В) 
    площадь.увеличить на аЬз(П.5 (А,В,Т}) конец программы 
    Саму программу обработки новой точки мы напишем по реализации исполнителя «Многоугольник»: 
    исполнитель Многоугольник 
    .СП: 
    .  1. начать работу (вх: А,В,С: точка R2) 
    .  2. обработать (вх: Т: точка R.2) 

    14б ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    — ребро (вх: А,В: точка R2) освещено из (вх: Т: точка R2) 
    : да/нет 
    — учесть удаление ребра {вх: А,В: точка R2)(ex: Т: точка  R2 
    3. периметр многоугольника	: число 
    4. площадь многоугольника	: число 
    5. кончить работу 
    объекты: Д	: дек элементов типа точка R2 
    число ребер: целое периметр ; число площадь : число 
    идеи реализации: 
    Вершины многоугольника хранятся в деке (последовательно). Порядок   вершин 
 в   деке   определяет  ориентацию ребер многоугольника.   Этот  порядок   
выбирается   так,  что   никакое ребро многоугольника не освещено ни из какой 
точки многоугольника 
    .    используемые исполнители: 
    Планиметр (П) конец описаний | --------
    программа начать работу (вх: А, В,С: точка R2) .   дано        : П.точки 
(А,В,С) не на одной прямой .   получить: ] создан треугольник правильной 
ориентации, т. а. | точки внутри треугольника не освещают его ребер 
    Д.начать работу .    Д.добавить элемент (В) в начало дека 
    если ребро {А,С) освещено из (В) .    . то 
    .   Д.добавить элемент (А) в начало дека .   Д.добавить элемент (С) в 
конец дека .  иначе .    .   Д.добавить элемент (С) в начало дека 
    .   Д.добавить элемент (А) в конец дека .   конец если 
    утв: [точки ДАВС не освещают его ребер; в частности, 
    ребро (Д.конец,Д.начало) не освещено из (В) ,   число ребер := 3 
    .   периметр      := n.R(A.B) + n.R(B,Q + n.R(C,A) .   площадь     :== abs 
(n.S(A,B,C}) конец программы 

    9. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА»	-             147 

    программа обработать {вх: Т: точка R2) 
    .   дано         : [ поступила новая точка Т 
    .   получить: | новая оболочка = conv (старая оболочка,Т) 
    Прежде всего надо понять, освещено ли из новой точки хоть одно ребро многоугольника: 
    . цикл число ребер раз 
    . . пока ребро {Д.конец,Д.начало) не освещено из {Т) 
    .   .   ВЫПОЛНЯТЬ 
    . .    Д. взять элемент из начала дека в {вых: X) . .    Д.добавить 
элемент {вх: X) в конец дека . конец цикла 
    утв : | ребро (Д.конец, Д.начало) освещено из (Т) или .	| и многоугольнике 
нет ми одного освещенного ребра 
    Дальше возникают два случая. Если в многоугольнике освещенных ребер нет, 
то это означает, что новая точка попала внутрь или на границу старой выпуклой 
оболочки, и, значит, больше ничего делать не надо. Если же ребро <Д.конец, 
Д.начало) освещено, то надо удалить псе освещенные ребра "и соединить концы 
оставшейся ломаной с новой точкой. При выполнении этих действий ппдо одновременно модифицировать периметр, площадь и 
число ребер оболочки: 
    . если ребро (Д. конец .Д.начало) освещено из (Т) то . .   учесть удаление 
ребра (Д.конец,Д.начало) (вх:Т)] 
    .	.	| -- у'1,1.'пп|. искошенные ребра из начала дека: 
    .	.	Д.взять элемент из начала дека в {вых : X) 
    .	.	цикл пока ребро {X,Д.начало) освещено из {Т) 
    .   .	.     ВЫПОЛНЯТЬ 
    . .	.   учесть удаление ребра {X,Д.начало) {вх:Т) 
    '. .	.   Д.взять элемент из начала дека в (вых: X) 
    . .	конец цикла 
    . .	Д.добавить элемент (вх : X) в начало дека 
    Фрагмент программы для удаления освещенных ребер из конца дека реализуйте самостоятельно. 
    . . | __ добавить новые ребра в точку Т: . . число ребер.увеличить на 2 
    . . периметр.увеличить на П.R (Д.конец,Т) + П. R {Т,Д.начало) ,-. , 
Д.добавить элемент (вх;Т) в начало дека 

    148 ГЛ. 2. НЕСКОЛЬКО  ПРИМЕРОВ   ПРОГРАММ 

    9. ПРОЕКТ «ВЫПУКЛАЯ ОБОЛОЧКА» 149 

    . конец если конец программы 
    программа ребро (их: А,В) освещено из <вх: Т): да/нет —=* (П.S (А,В,Т) < 
0.0) или (П.S (А,В,Т) = 0.0 и П.точка (Т) не внутри отрезка (А,В» 
    программа учесть удаление ребра (вх: А, В) (вх: Т : точка R2) . дано       
 : А, В: точка R2 [удаляемое ребро и ребро (А,В) освещено из (Т) . получить: | 
число ребер, периметр и площадь соответствующим 
    |  образом изменены 
    .    число ребер.уменьшить на 1 
    периметр.уменьшить на n.R(A.B) .   площадь.увеличить на abs (П.8 (А,Т,В}) 
конец программы 
    = периметр = площадь = Д.кончить   работу 
    :да/нет 
    :да/нет :число :число 
    программа периметр многоугольника: число = 
    программа площадь многоугольника : число 
    программа кончить работу 
    конец исполнителя! .— -~_=,_= = «, = = = = а = = _=„ ======,==,=«, 
    Третий  шаг  декомпозиции.  Осталось  реализовать  исполнителя «Планиметр»: 
    исполнитель Планиметр . СП: 
    ,     1. точки (вх: А, В, С : точка R2) на одной прямой .     2. точка (вх 
: Т : точка R2) внутри отрезка 
    (вх: А, В: точка R2) 3. R(nx : А,В: точка R2) .     4. 5(вх:А,В,С:точка R2) 
    . типы: 
    точка R2 = запись (X,Y: число) конец описаний |   _ — — _ — _- —— ____ — 
__- — ____—_ 
    программа точки (вх:А,В,С) на одной прямой:да/нет == 
    (S(A,B,C) = 0) 
    программа точка (вх:Т) внутри отрезка (вх : А,В): да/нет == 
    (R(A,T)+R(T,B)<R<A,B» 
    программа R(A,B): число == sqrt (А.Х—В.Х) ** 2 + (A.Y — 
    B.Y)**2) 
    программа S (А,В,С): число == ((А.Х-С.Х) * (B.Y-C.Y) 
    (A.Y-C.Y) * (В.Х-С.Х)) * О.б конец исполнителя 1 
    Ориентированная   площадь   треугольника   считается   как  поло* вина 
площади параллелограмма, натянутого на векторы СА и СВ, 

    ЗАДАЧИ И УПРАЖНЕНИЯ 

    1, Пользуясь исполнителем «Выпуклая оболочка» как базовым, 
    напишите программу 
    программа периметр выпуклой оболочки множества (BJC : М): число 
    ,  дано       : М: множество элементов типа точка R2 
    • получить: | ответ=периметр выпуклой оболочки точек множества 
    2. Упростите проект «Выпуклая оболочка», считая, что работа начинается с 
трех точек в общем положении, 
    3. Нарисуйте состояние дека  после  поступления  в  указанном порядке 
следующих точек (рис. 9.8). 
    4. Опишите, что произойдет, если изменить знак в программе^ 
й1111Л11;1И|>у|()1Ц('П огшмцспмость ребра из точки, т. е. написать 
программа ребро (вх:Л,В) освещено из (вх: Т): да/нет == (11.S (Л,Т,В» 0.0) 
или (П.5 (А,Т,В} = 0.0 и П.точка (Т) не внутри отрезка (А.В» 
    Решите упражнение 3 в этой ситуации. 
    5. Добавьте к исполнителю  «Выпуклая  оболочка» предписание 
    точка <вх : Т : точка  R2> .внутри выпуклой  оболочки     : да/нет 
    и реализуйте его. 
    6. Добавьте к исполнителю «Выпуклая оболочка» предписания 
    а) диаметр выпуклой оболочки, 
    б) центр тяжести вершин выпуклой оболочки 
    и   реализуйте   их   аналогично   предписаниям   «периметр»   и   «площадь». 

    150 ГЛ. 2. НЕСКОЛЬКО   ПРИМЕРОВ   ПРОГРАММ 

    7. Переделайте исполнителя «Выпуклая оболочка» так, чтобы он мог 
обрабатывать точка трехмерного пространства, расположен-! ные в одной 
плоскости (если новая точка лежит вне плоскости ста* рых, исполнитель должен 
давать отказ). 
    8. Придумайте понятие освещенности^ при котором добавление точки к 
двуугольнику будет происходить по тому же алгоритму, что и добавление точки к 
многоугольнику. (Разрешается наличие нулевых и развернутых углов, т. е. ребра 
выпуклой оболочки могут быть расположены на одной прямой.) 
    9. Переделайте проект «Выпуклая оболочка последовательно поступающих точек 
плоскости» в проект «Выпуклая оболочка последовательно поступающих точек 
плоскости Лобачевского (модель Пуанкаре)». 
    10. Придумайте алгоритм построения выпуклой оболочки, основанный на 
хранении неупорядоченного множества ребер, где (с математической точки зрения) 
ребро — это неупорядоченная пара точек плоскости, 
    11. Реализуйте выпуклую оболочку последовательно поступающих точек в 
трехмерном пространстве, считая, что работа начинается с четырех точек в общем 
положении (используйте обобщение алгоритма задачи 10). 
    12. Сделайте задачу 11  в N-мерном пространстве при N = 10, 
