| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Выч.геом.] Пара точек ближайшая в метрике L1 |
| Автор: susl 26.5.2007, 01:29 |
| На плоскости заданы два множества А и В, каждое из которых образует "лесницу" (совпадает с множеством своих максимумов в отношении доминирования). Найти за линейное время пару точек a, b ближайшую по метрике L1, a из A, b из B. L1(a, b) = |ax - bx| + |ay - by| a доминирует b <=> (ax >= bx && ay > by) || (ax > bx && ay >= by) |