Тут если доказать, что количество медиан зависит только от n (кол-ва точек) и не зависит от расположения точек, то можно рассматривать равносторонний многоугольник с n вершинами, у которого n/2 "медиан".
А вот как строго доказать первый факт надо подумать...
Медианы
А можно так.
Пусть всего n точек.
Тогда каждой точке x, очевидно, соответствует строго одна точка y из оставшихся n-1 точки, так чтобы пара (x,y) образовывала медиану (такая медиана существует для любой x, т.к. n-1 нечетно и никакие 3 точки не лежат на прямой).
Вспоминаем правило рукопожатия (если пара(x,y) образует медиану, то пара (y,x) образует ту же медиану, которую мы уже посчитали) и получаем результат - n/2
Пусть всего n точек.
Тогда каждой точке x, очевидно, соответствует строго одна точка y из оставшихся n-1 точки, так чтобы пара (x,y) образовывала медиану (такая медиана существует для любой x, т.к. n-1 нечетно и никакие 3 точки не лежат на прямой).
Вспоминаем правило рукопожатия (если пара(x,y) образует медиану, то пара (y,x) образует ту же медиану, которую мы уже посчитали) и получаем результат - n/2
Да уж...
Значит предположение "если доказать, что количество медиан зависит только от n" не верно.
Тут еще один примерчик в голову пришел - (0,0)(0,4)(4,0)(1,1)(1,2)(2,1) - 6 точек, 6 медиан.
По любому условия прийдется ставить на взаимное расположение точек...
Правда для одного случая задача решена %))
В остальном - трудно сказать.
Значит предположение "если доказать, что количество медиан зависит только от n" не верно.
Тут еще один примерчик в голову пришел - (0,0)(0,4)(4,0)(1,1)(1,2)(2,1) - 6 точек, 6 медиан.
По любому условия прийдется ставить на взаимное расположение точек...
Правда для одного случая задача решена %))
В остальном - трудно сказать.
А какого объема множество, с которым прийдется работать?
Если небольшое - то почему бы просто не перебрать все пары и для каждой посмотреть, является ли она медианой (подставлять в уравнение прямой, полученной по двум точкам значение третьей точки, чтобы определить, с какой стороны эта третья точка, т.е. сравнивать полученно значение с 0).
Т.е. порядка n(n-1)/2 операций на перебор ребер и порядка (n-2) операции на перебор точек.
Итого такой алгоритм будет за O(n^3) находить не только количество медиан, но и все медианы.
Или надо более быстрый алгоритм?
Если небольшое - то почему бы просто не перебрать все пары и для каждой посмотреть, является ли она медианой (подставлять в уравнение прямой, полученной по двум точкам значение третьей точки, чтобы определить, с какой стороны эта третья точка, т.е. сравнивать полученно значение с 0).
Т.е. порядка n(n-1)/2 операций на перебор ребер и порядка (n-2) операции на перебор точек.
Итого такой алгоритм будет за O(n^3) находить не только количество медиан, но и все медианы.
Или надо более быстрый алгоритм?
-
Naeel Maqsudov
- Сообщения: 2551
- Зарегистрирован: 20 фев 2004, 19:17
- Откуда: Moscow, Russia
- Контактная информация:
Все естественно порушится, если хотя бы у двух точек координата Y будет одинакова.