Тема: Выпуклая оболочка
Задача: дан многоугольник без само пересечений (все вершины различны, количество вершин от 3 до 1000,координаты от -10000 до 10000, вершины в порядке следования против часовой) и расстояние (от 1 до 1000), ближе которого не может подходить к многоугольнику непрерывная линия . Нужно найти минимальную длину этой линии.
Я сначала строю выпуклую оболочку: ищется нижняя правая точка (она точно входит в оболочку) и от неё строится оболочка (обходом всех вершин с проверкой на правый поворот).
Получается неправильный ответ на 8 тесте.
Подскажите, что не так.
TYPE t=record
x,y:real;
end;
var f,f1:text; d,a:array[1..2010] of t; n,l,k,i,min:integer; r:real;
function ok(a,b,c:t):boolean; {правда - если с справа от вектора ab и наоборот}
begin
if (a.x-c.x)*(b.y-c.y)+(b.x-c.x)*(c.y-a.y)<0 then ok:=true else ok:=false;
end;
function len(a,b:t):real;
begin
len:=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
end;
begin
reset(f,'wall.in');
rewrite(f1,'wall.out');
read(f,n,l);
min:=1;
for i:=1 to n do begin
read(f,d[i].x,d[i].y);
if (d[i].y<d[min].y) or ((d[i].y=d[min].y) and (d[i].x<d[min].x)) then min:=i;
end;
close(f); {считаны точки и найден минимум(крайняя снизу и справа точка)}
for i:=1 to min-1 do d[n+i]:=d[i];
{теперь элементы упорядочены относительно минимума}
a[1]:=d[min]; a[2]:=d[min+1]; k:=3;
for i:=min+2 to n+min-1 do
if ok(a[k-2],a[k-1],d[i]) then begin a[k]:=d[i]; inc(k) end else a[k-1]:=d[i];
r:=0;k:=k-1;
for i:=1 to k-1 do r:=r+len(a[i],a[i+1]);
r:=r+len(a[1],a[k]);
write(f1,r+2*pi*l:0:16);
close(f1);
end.