29K
26 мая 2007 года
susl
1 / / 26.05.2007
На плоскости заданы два множества А и В, каждое из которых образует "лесницу" (совпадает с множеством своих максимумов в отношении доминирования). Найти за линейное время пару точек a, b ближайшую по метрике L1, a из A, b из B.
L1(a, b) = |ax - bx| + |ay - by|
a доминирует b <=> (ax >= bx && ay > by) || (ax > bx && ay >= by)