Помогите с задачкой

← →
Windows © (2007-01-08 18:00) [0]

Расстоияние между двумя множествами точек-это расстояние между наиболее близко расположенными точками этих множеств. Найти расстояние между двумя заданными множествами точек на плоскости!

с чего начать решение этой задачи?)
если с учебника математики, то прямо так и скажите. Мне кажется, здесь чего-то не хватает в условии...

← →
try (2007-01-08 18:10) [1]

Начать с учебника математики (геометрии). В условии всего хватает.

← →
Windows © (2007-01-08 18:14) [2]

спасибо)

← →
AlexanderMS © (2007-01-08 18:27) [3]

Если все точки множеств заданы, значит, известны координаты точек (x, y).
Если множество недостаточно объёмное, то можно простым перебором. Надеюсь, Вам известна формула расстояния между двумя точками:
d = sqrt(sqr(x1 - x2) + sqr(y1 - y2))
(синтаксис Паскаля). Она есть в учебнике геометрии.
А так:

Вычислять расстояния между каждыми двумя точками и выбрать
наименьшее. Оно и будет искомым.

> Мне кажется, здесь чего-то не хватает в условии...

Откуда задача?

← →
AlexanderMS © (2007-01-08 18:28) [4]

> В условии всего хватает.

Да, хотя не помешало бы уточнение.

← →
ors_archangel © (2007-01-08 22:20) [5]

> [0] Windows, [3] AlexanderMS

Локальная оптимизация: так как во всех случаях странвниваются евклидовые расстояния, то можно использовать формулу
d = sqr(x1 - x2) + sqr(y1 - y2) (*)
т.к. x1 < x2 => sqrt(x1) < sqrt(x2).
Предлагаю в качестве глобальной оптимизации для начала строить quadtree для всех точек вместе, мотом использовать алгоритм [3] с облекчённой формулой (*) в тех квадратах, где будут точки из обоих множеств

← →
vidiv © (2007-01-08 22:25) [6]

> ors_archangel © (08.01.07 22:20) [5]

а что быстрее посчитается, это:

> d = sqr(x1 - x2) + sqr(y1 - y2)

или это:
d2 = abs((x1-x2)*(y1-y2))

По идее по d2 тоже можно сравнивать =)

← →
vidiv © (2007-01-08 22:35) [7]

А как, кстати, множества задаются?

← →
Servelat © (2007-01-08 22:38) [8]

> d2 = abs((x1-x2)*(y1-y2))

Точки с одинаковой абсциссой (или ординатой) тогда находятся на условном расстоянии 0? И как тогда сравнить расстояния между парами таких точек? Как минимум поэтому данная формула не подойдет.

> vidiv © (08.01.07 22:25) [6]

Развиваю идею: сначала производим линейное сравнение:
d3 = min(abs(x1-x2), abs(y1-y2));
Если одна пара точек линейно ближе друг к другу, чем другая пара, то они ближе бруг к другу и в евклидовом смысле, а вот если линейно пара точек равно другой паре, то нужно сделать проверку по формуле [5] (*).

> А как, кстати, множества задаются?

Видимо, точки в двумерном пространстве, см. [0]

> а что быстрее посчитается

примерно одинаково, а вот d3 быстрее d1 больше, чем в два раза, когда я тестировал 3D-вариант, в 2D, конечно, эффекта меньше будет :(

> Точки с одинаковой абсциссой (или ординатой) тогда находятся
> на условном расстоянии 0? И как тогда сравнить расстояния
> между парами таких точек? Как минимум поэтому данная формула
> не подойдет.

Да.... Придётся заменить min на max

Помогите с задачкой Найти похожие ветки