Определить, лежат ли точки по одну сторону от прямой - C (СИ)
Формулировка задачи:
Дорогие, прошу помощи с алгоритмом по задаче!
Задано множество M точек на плоскости. Определить, верно ли, что для каждой точки А из М существует точка В из М (А<>В) такая, что не существует двух точек множества М, лежащих по разные стороны от прямой АВ
помогите разобраться в смысле задания..допустим тут можно использовать медиану?
Заранее спасибо))
Решение задачи: «Определить, лежат ли точки по одну сторону от прямой»
textual
Листинг программы
// (теорема) [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).