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