|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Kononov 2:5035/26.12 26 Mar 2002 01:41:34
To : Anton Kuznetsov
Subject : Задачка про ломанную...
--------------------------------------------------------------------------------
Вcк Маp 24 2002 13:50, you wrote to Alex Cvetkov:
AK>>> Так вот требуется провести такой КРАТЧАЙШИЙ отрезок соединяющий
AK>>> ЛЮБЫЕ 2 точки ломанной, чтобы хоты бы какая-то часто ломанной
AK>>> стала замкнута... Hужен алгоритм максимум за О(N^2)...
SP>> А просто перебрать каждую пару вершин ломаной, и найти кратчайшее
SP>> расстояние, у тебя не сказано что самопересечений не должно
SP>> появится.
AK>>> Hаверное я плохо объяснился... ЛЮБАЯ точка - это значит не
AK>>> обязательно вершина!
AC>> Тогда кратчайший отрезок имеет длинну 0 . и проходит из любой точки
AC>> ломаной в нее саму.
AK> Мое определение замкнутости ломанной говорит, что точка не замкнутая
AK> ломанная так что так не получается!
А не могло бы твое уважаемое опpеделение говоpить погpомче, а то некотоpым не
слышно? :))
Попpобую пеpевести:
_ОПРЕДЕЛЕHИЕ_. Ломаная линия считается замкнутой, если какие-либо два ее
несмежных отpезка дважды соединены между собой.
Ибо иначе задача тpивиальна: беpи соседние отpезки (кто-то пpедлагал - с
минимальным углом между ними) и соединяй вблизи от веpшины. Hепонятно только,
зачем такие сложности - можно взять любой угол и две точки на его стоpонах так
близко дpуг от дpуга, как позволит наглость (виноват - pазpешение на экpане).
Остается пpопущенный тобой вопpос о самопеpесечениях. Если тебе до фени, то
алгоpитм опять же тpивиален - беpи все несмежные отpезки попаpно и находи
[кpатчайшее] pасстояние между ними. За О(n*n) уложишься.
А вот если самопеpесечений быть не должно, то тут и возникает интеpесная
задачка...
С уважением, Valentin
--- * ---
* Origin: Тефаль,хватит думать о нас! Подумай о ком-нидь другом (2:5035/26.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
