|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Skazik 2:5061/6.61 30 Mar 2002 00:10:41
To : Yurij Borisoff
Subject : Определение границы...
--------------------------------------------------------------------------------
Yurij Borisoff => Alexey Skazik 29 Мар 02 19:01 :
AS>> Идеи? Что-либо кроме простого перебора по парам точек, с
AS>> выяснением есть ли что-либо с одной или другой стороны
AS>> проведённой ч/з них прямой? :) Границы прямоугольной области, в
AS>> которой гарантированно находится множество -известны.
YB> Делаем просто: сперва находим самую нижнюю точку (если их несколько,
YB> берем самую левую из них) /это будет х1, у1 /, затем точка 2 находится
YB> такая, что угол м/у векторами (-1, 0) и (х2-х1, у2-у1) минимален, etc.
YB> Сложность О(n^2). Сразу получаем упорядоченную границу.
Ж:) Вроде, подходит. Буду писать. Спасибо!
With best wishes!
Alexey.
--- GoldED+/W32 1.1.3
* Origin: ДДННН --------------------------------------------- НН (2:5061/6.61)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
