Определить, лежат ли точки по одну сторону от прямой - 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).
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д