Выпуклая оболочка

Для конечного множества точек выпуклой оболочкой всегда будет выпуклый многоугольник, все вершины которого есть точки этого множества, а все остальные точки множества оказываются внутри или на сторонах этого многоугольника. Наша задача найти вершины выпуклой оболочки среди заданного множества точек. Будем перечислять точки в порядке их обхода против часовой стрелки. Наиболее простым является алгоритм Джарвиса. Перечисление точек начнем с правой нижней точки P1. Следующей точкой оболочки будет точка P2, при выборе которой все остальные точки лежат слева от вектора (функции vect). Очевидно, что для выбора очередной точки нужно проверять на это условие все множество точек. Если подходящих точек несколько, то выбираем точку, для которой длина вектора максимальна (функция dist). Выбранные точки записываются в массив b. Приведенная программа целиком заимствована из работы [5].

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

Внимательно изучите программу, посмотрите, как авторы проверяют замыкание оболочки.

Попробуйте написать программу самостоятельно, этот алгоритм часто встречается в задачах олимпиад. Там, конечно, не будет явно звучать задача построения выпуклой оболочки, но вы должны увидеть в «замысловатом» сюжете, что это именно так.

Если вы не знакомы с типом Record, то следует читать [1] или удовлетвориться нашим кратким пояснением. Запись (Record) это структура данных, состоящая из фиксированного числа компонент (полей). В отличие от массива компоненты могут быть различных типов. Для ссылки поля именуются. Например, в программе поле xв массиве a, будет доступно по имени a[i].x, а поле y по имени a[i].y. В предыдущих примерах мы использовали для координат точек два массива.

Type vv=Record

x, y:longint;

End;

Var a, b: array[1..101] of vv;

min, m, i, j, k, n:integer;

Function vect(a1, a2, b1, b2: vv):longint;

{косое произведение векторов а1а2 и в1в2}

Begin

vect:=(a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y)

End;

Function dist2(a1, a2:vv): longint;

{квадрат длины вектора}

Begin

dist2:=sqr(a2.x-a1.x)+sqr(a2.y-a1.y)

End;

Begin

Readln (n); { количество точек}

For i:=1 to n do Read (a[i].x, a[i].y);

{ ищем правую нижнюю точку}

m:=1;

For i:=2 to n do

if a[i].y<a[m].y then m:=i

else

if (a[i].y = a[m].y) and

(a[i].x > a[m].x) then m:=i;

{запишем ее в массив выпуклой оболочки «в»}

b[1]:=a[m];

{и переставим на первое место в исходном массиве}

a[m]:=a[1];

a[1]:=b[1];

k:=1;

min:=2;

repeat

{ищем очередную вершину выпуклой облочки}

For j:=2 to n do

if (vect (b[k],a[min],b[k], a[j])<0) or

((vect (b[k],a[min],b[k], a[j])=0) and

(dist2 (b[k], a[min])< dist2(b[k], a[j])))

then min:=j;

k:=k+1;

{записана очередная вершина}

b[k]:=a[min];

min:=1;

until ( b[k].x=b[1].x) and (b[k].y=b[1].y);

{пока ломаная не замкнется}

For j:=1 to k-1 do

Writeln(b[j].x, ' ',b[j].y);

readln

end.