Определить, лежат ли точки по одну сторону от прямой - C (СИ)

Формулировка задачи:

Дорогие, прошу помощи с алгоритмом по задаче! Задано множество M точек на плоскости. Определить, верно ли, что для каждой точки А из М существует точка В из М (А<>В) такая, что не существует двух точек множества М, лежащих по разные стороны от прямой АВ помогите разобраться в смысле задания..допустим тут можно использовать медиану? Заранее спасибо))

Решение задачи: «Определить, лежат ли точки по одну сторону от прямой»

Листинг программы

// (теорема) [url]http://www.cyberforum.ru/cpp-beginners/thread614846.html[/url]
// (пример) [url]http://www.cyberforum.ru/cpp-beginners/thread614829.html[/url]
 
#include <stdio.h>
 
class point2f
{
 public:
  float x;
  float y;
 
  point2f(){ x = 0.0; y = 0.0;}
  point2f(float a1, float b1){ x = a1; y = b1;}
};
 
class line
{
 public:
  float A;
  float B;
  float C;
 
  line(point2f* d1, point2f* d2)
  {
   A = d2->y - d1->y;
   B = d1->x - d2->x;
   C = d2->x*d1->y - d1->x*d2->y;
  }
 
  int check(point2f* d1, point2f* d2)
  {
   float r1, r2, r3;
    r1 = A*d1->x + B*d1->y + C;
    r2 = A*d2->x + B*d2->y + C;
    r3 = r1*r2;
 
   if (r3<0)
    return 1;
   else
    return 0;
  }
};
 
class s1
{
 public:
  point2f* y;
  int sz;
 
  s1(int n)
  {
   y = new point2f[n];
   sz = n;
  }
 
  ~s1()
  {
    delete [] y;
  }
 
  // Задано множество M точек на плоскости.
  // Определить, верно ли, что для каждой точки А из М
  // существует точка В из М (А<>В) такая,
  // что не существует двух точек множества М,
  // лежащих по разные стороны от прямой АВ
 
  // предполагаем что y проинициализирован точками
  int check()
  {
    int i, j, k, l;
    line* ab;
    int m = 0;
    // выборка первой точки A
    for(i=0;i<sz; i++)
    {
      // выборка второй точки B
     for(j=0;j<sz; j++)
     {
       // выборка третьей точки C не равной A и B
       for(k=0;k<sz; k++)
       {
         //строим прямую AB
         ab = new line(&(y[i]), &(y[j]));
         if (k != i && k != j) // не равной A и B
         {
           // выборка четвертой точки не равной A и B и C
           for(l=0;l<sz; l++)
           {
            if (l != i && l != j && l != k) // не равной A и B и C
            {
              // проверка
              m = ab->check(&(y[k]), &(y[l]));
              if (m)
               return 1;
            }
           }
         }
         // удаляем прямую ab
         delete ab;
       }
     }
    }
 
   return 0;
  }
 
};
 
 
 
int main()
{
 
s1* t;
t = new s1(3);
(t->y[0]).x = 2.0;
(t->y[0]).y = 1.0;
 
(t->y[1]).x = 3.0;
(t->y[1]).y = 0.0;
 
(t->y[2]).x = -1.0;
(t->y[2]).y = 0.0;
/*
(t->y[3]).x =  0.9;
(t->y[3]).y = 0.5;
*/
printf("%d", t->check());
return 0;
}

Объяснение кода листинга программы

Создается класс point2f для представления точки на плоскости с координатами (x, y).
Создается класс line для представления прямой на плоскости с координатами A, B и C (точка, направленный вектор).
Создается класс s1 для работы с множеством точек на плоскости.
В конструкторе класса s1 инициализируется массив точек y.
В методе check() класса s1 проверяется, что для каждой точки А из множества M существует точка В, такие что не существует двух точек из M, лежащих по разные стороны от прямой АВ.
Для этого в цикле перебираются все возможные комбинации точек А и В.
Для каждой пары точек А и В строится прямая AB и проверяется, что она пересекает какую-либо точку из множества M (точка C).
Если прямая AB пересекает точку C, то это значит, что существуют две точки из M, лежащие по разные стороны от прямой AB.
Если таких точек нет, то возвращается 0, иначе - 1.
В методе main() создается экземпляр класса s1 с тремя точками (2.0, 1.0), (3.0, 0.0) и (-1.0, 0.0).
Затем вызывается метод check() для этого экземпляра класса s1.
Результат проверки выводится на экран.
В данном случае результатом будет 0, так как прямая, проходящая через точки (2.0, 1.0) и (-1.0, 0.0), пересекает точку (3.0, 0.0).