Вычислительная геометрия на С

[Soull]

Заданы координаты N точек. Определить те две точки, проведенная через которые прямая делит имеющиеся точки пополам.

[Z1000000]

В чем проблема ?

[Soull]

Сообщение от Z1000000

В чем проблема ?

Проблема , как эти точки найти.

[Z1000000]

Найти их просто: перебором всех пар точек и вычислением для остальных точек по какую сторону от образованной прямой они находятся.

Если находится такая пара, что половина оставшихся точек находится по одну, а половина по другую сторону - то , по крайней мере, одна пара точек найдена. Если не находится - то нет такой пары

[Soull]

Сообщение от Z1000000

перебором всех пар точек и вычислением для остальных точек по какую сторону от образованной прямой они находятся.(

Я не могу понять , как можно проверить по какую сторону они находятся и сколько их. Не доходит до меня

[Z1000000]

Для пары точек , образующих прямую, с координатам X1,Y1 и X2,Y2 и точки положение которой нужно проверить с координатами X,Y строишь квадратную матрицу порядка 3:
X1 X2 X
Y1 Y2 Y
1 1 1
Находишь определитель этой матрицы. Если определитель:
Равен 0 - точка лежит на прямой - это тебе не нужно.
Если положителен - то точка лежит по одну сторону от прямой.
Если отрицателен - по другую сторону.
Вот и все. Как в сказке про Алису и голубую гусеницу на грибе

[sabbathist]

Тут еще вопрос в ограничениях. Ваше решение имеет сложность O(n^3). Если точек будет не больше 100, то все хорошо. А если больше - тут уже совсем другая история...

[Soull]

Сообщение от Z1000000

Для пары точек , образующих прямую, с координатам X1,Y1 и X2,Y2 и точки положение которой нужно проверить с координатами X,Y строишь квадратную матрицу порядка 3:
X1 X2 X
Y1 Y2 Y
1 1 1
Находишь определитель этой матрицы. Если определитель:
Равен 0 - точка лежит на прямой - это тебе не нужно.
Если положителен - то точка лежит по одну сторону от прямой.
Если отрицателен - по другую сторону.
Вот и все. Как в сказке про Алису и голубую гусеницу на грибе

Спасибо большое))) Это гениально просто