Developing.ru

Все естественно порушится, если хотя бы у двух точек координата Y будет одинакова.

А какого объема множество, с которым прийдется работать?
Если небольшое - то почему бы просто не перебрать все пары и для каждой посмотреть, является ли она медианой (подставлять в уравнение прямой, полученной по двум точкам значение третьей точки, чтобы определить, с какой стороны эта третья точка, т.е. сравнивать полученно значение с 0).

Т.е. порядка n(n-1)/2 операций на перебор ребер и порядка (n-2) операции на перебор точек.
Итого такой алгоритм будет за O(n^3) находить не только количество медиан, но и все медианы.

Или надо более быстрый алгоритм?

Да уж...
Значит предположение "если доказать, что количество медиан зависит только от n" не верно.
Тут еще один примерчик в голову пришел - (0,0)(0,4)(4,0)(1,1)(1,2)(2,1) - 6 точек, 6 медиан.

По любому условия прийдется ставить на взаимное расположение точек...
Правда для одного случая задача решена %))

В остальном - трудно сказать.

А можно так.
Пусть всего n точек.
Тогда каждой точке x, очевидно, соответствует строго одна точка y из оставшихся n-1 точки, так чтобы пара (x,y) образовывала медиану (такая медиана существует для любой x, т.к. n-1 нечетно и никакие 3 точки не лежат на прямой).

Вспоминаем правило рукопожатия (если пара(x,y) образует медиану, то пара (y,x) образует ту же медиану, которую мы уже посчитали) и получаем результат - n/2

Тут если доказать, что количество медиан зависит только от n (кол-ва точек) и не зависит от расположения точек, то можно рассматривать равносторонний многоугольник с n вершинами, у которого n/2 "медиан".

А вот как строго доказать первый факт надо подумать...