Developing.ru

Помогите сделать программу (или подсказать как ее делать). Не могу даже понять как к ней подойти.

Медианой множества, состоящего из четного числа точек плоскости, никакие три из которых не лежат на одной прямой, называется прямая, соединяющая две точки множества, с обеих сторон от которой лежит равное число точек.
Даны действительные числа x1, y1, x2, y2, …, xn, yn (n – нечетное число). Найти число медиан множества точек с координатами (x1, y1),( x2, y2),…( xn, yn) в предположении, что никакие три точки этого множества не лежат на одной прямой.

Ничего более умного, чем полный перебор мне сейчас не приходит в голову.

1. Вычисляем все возможные варианты пар точек.
2. Для каждой пары строим уравнение прямой, проходящей через эти две точки.
3. Подставляем в уравнение каждую из оставшихся точек множества и смотрим на знак результата: если точка лежит в той же полуплоскости, в которой лежит начало координат, значит знак будет положительным, если в другой, то отрицательным. Таким образом получится посчитать сколько точек лежит по одну сторону от прямой, а сколько по другую.

Ещё раз повторяю - то первое решение, которое пришло в голову. Возможно, есть более изящное.

Здесь необходимо уточнение: если имеются точки А и В, то отрезки АВ и ВА считать как один и тот же отрезок или как два разных? Если это один отрезок, то количество паросочетаний (т.е. отрезков) вычисляется по формуле N*(N-1)/2, где N - количество точек в множестве. Если же это два разных отрезка, то их количество составит N*(N-1).
Для определения положения точки относительно отрезка можно воспользоваться алгоритмом, который предложил WinMain в своей статье: http://winmain.epage.ru/geom/page.html

AB и BA это одно и тоже согласно хотя бы тому, что уравнение прямой будет одним и тем же.

мне без разницы, главное решить, потому что я это задание не могу понять как писать