множество точек и прямая..., нужен алгоритм решения Опции

[MI666]

Задано множество M точек на плоскости. Определить верно ли, что для каждой точки A, принадлежалей множеству M существует точка B из множества M (A<>B) такая, что не существует двух точек множества M, лежащих по разные стороны от прямой AB.

thanks...

[trminator]

Пусть есть прямая, заданная уравнением ax + by + c = 0.
Точки A1(x1, y1) и A2(x2, y2) находятся по одну сторону от прямой, если выражения
a*x1 + b*y1 + c
a*x2 + b*y2 + c
имеют один знак.

То есть можно решить "по-тупому": перебрать все пары точек (где-то в соседней теме перебирали), для каждой пары построить прямую и проверить все оставшиеся точки...

[zx1024]

По точкам нужно построить выпуклую оболочку (многоугольник).
Если остались точки, лежащие внутри получившегося многоугольника, то "не верно", если нет, то "верно".