Ещё задачка...

[noname00.pas]

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

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

[Apis.NET]

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

[noname00.pas]

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

[vasketsov]

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

[noname00.pas]

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

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

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

[vasketsov]

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

[Apis.NET]

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

[noname00.pas]

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

[Apis.NET]

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