Реферат: Геометрические задачи на олимпиадах по информатике

Таким образом, при решении данной задачи в случае изначально целочисленных координат мы полностью можем избежать применения вещественной арифметики, а, следовательно, избавиться от потери точности вычислений. В противном случае, в решение могут быть включены “лишние” точки, близкие к границе выпуклой оболочки или не учтены некоторые из “нужных” точек. Сложность данного алгоритма составит O (kN ), где k — количество точек в выпуклой оболочке, в худшем случае равное N . Существуют алгоритмы решения этой задачи, основанные на предварительной сортировке точек исходного множества, например, по значению угла в полярной системе координат с центром в одной из точек выпуклой оболочки, с вычислительной сложностью O (N logN ) (алгоритм Грехема). То есть наиболее трудоемкой задачей оказывается именно сортировка исходных точек.

Приведем программу решения данной задачи алгоритмом Джарвиса:

var a, b: array [1..100] of record

x,y:integer ;

f:boolean

end;

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

begin

readln(n);

for i:=1 to n do

begin

read(a[i].x, a[i].y);

a[i].f:=false

end ;

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

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].f:=true ;

k:=1;

repeat

min:=1;

{ищем первую еще свободную точку}

while a[min].f do inc(min);

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

for j:=1 to n do