Дан многоугольник на плоскости. Нужно окружить его линией наименьшей длины таким образом, чтобы она не приближалась к многоугольнику ближе чем на расстояние L.
Во входном текстовом файле в первой строчке через пробел числа N(количество вершин, не более 1000) и L. Далее на N строках пары кообринат вершин через пробел в порядке обхода по часовой стрелке. В выходной файл нужно вывести единственное число - длину получившейся линии.

ПС. Я же не прошу вас публиковать тексты программ, просто напишите, как нужно решать ;)

noname00.pas Писец ты сам то понял что сказал7 Ты с азов начни!

Apis.NET
Куда же проще то? Это вобще на геометрию задачка :)

1. По многоугольнику строится его минимальная выпуклая оболочка (ВО) (единственная). Дальше вся работа с ней.
2. Описываем вокруг каждой вершины ВО окружность радиуса L.
3. Проводим попарно внешние касательные для соседних окружностей
4. Считаем длину исходя из точек касания.
5. Идем за пивом.

vasketsov
Верно... А можно ещё проще. Периметр выпуклой оболочки + 2*pi*L
;)

П.С. Это была задача D с прошедшего вчера полуфинала ACM (NEERC) ИМХО самая простая...

Apis.NET
Нужно ли объяснять, как строится выпуклая оболочка?

noname00.pas
>>Верно... А можно ещё проще. Периметр выпуклой оболочки + 2*pi*L
Да, не сообразил :)))

noname00.pas Человеку который считает что самое большое счастье в его жизни это отмена экзамена по геометрии в 7 классе? Думаю что надо.

Apis.NET
Читай тему "Построение выпуклой оболочки методом Джарвиса"

Ладно, будет время прочту.