Проблемы с геометрической задачей
драсте! вот у мну такая задача есть, там даны координаты некоторого количества точек на плоскости, нужно выписать уравнение прямой (в любом виде), которая делит плоскость на 2 полуплоскости, содеражщие одинаковое количество точек! массив точек хранить в динамической памяти...
ну с кучей проблем нету никаких... проблема с тем, что я дажне не знаю, как к ней подступиться... понимаю, что скорее всего, нужно рассматреть 2 случая - четное число точек и нечетное... если нечетное, то проводить прямую через одну из точек! вот только как именно определить уравнение прямой, не пойму!
Если у кого-либо есть идеи, пожалуйста, отпишитесь! код сильно не интересует, интересует именно алгоритм! Заранее всем спасибо!!!
ну с кучей проблем нету никаких... проблема с тем, что я дажне не знаю, как к ней подступиться... понимаю, что скорее всего, нужно рассматреть 2 случая - четное число точек и нечетное... если нечетное, то проводить прямую через одну из точек! вот только как именно определить уравнение прямой, не пойму!
Если у кого-либо есть идеи, пожалуйста, отпишитесь! код сильно не интересует, интересует именно алгоритм! Заранее всем спасибо!!!
Например,
1.берешь произвольную точку А
2.берешь произвольную точку В
3.Проводишь прямую через них
4.проверяешь количество точек с каждой стороны
5.Допустим, слева больше.
6.Сдвигаешь точку В вокруг точки А на 45 градусов и идешь к пункту 3
При каждом следующем проходе угол уменьшаешь в два раза
1.берешь произвольную точку А
2.берешь произвольную точку В
3.Проводишь прямую через них
4.проверяешь количество точек с каждой стороны
5.Допустим, слева больше.
6.Сдвигаешь точку В вокруг точки А на 45 градусов и идешь к пункту 3
При каждом следующем проходе угол уменьшаешь в два раза
а вот вышеупомянутые точки А и В - это точки из заданного множества или произвольные? ну если произвольные, то я вообще могу брать любые 2 точки? напрмер (0,0) и (1,1) ?
как я понимаю, проверка того, находится ли точка выше или ниже заключается в подстановке ее координат в уравнение прямой??
как я понимаю, проверка того, находится ли точка выше или ниже заключается в подстановке ее координат в уравнение прямой??
Цитата:
Например,
1.берешь произвольную точку А
2.берешь произвольную точку В
3.Проводишь прямую через них
4.проверяешь количество точек с каждой стороны
5.Допустим, слева больше.
6.Сдвигаешь точку В вокруг точки А на 45 градусов и идешь к пункту 3
При каждом следующем проходе угол уменьшаешь в два раза
мне кажется не будет такое работать - как определить в какую сторону поворачивать?
если когда слева больше поворачивать против часовой стрелки, а меньше - по, то ерунда получается:
точка А = (0, 0)
В = (0, 1)
Множество состоит из одной точки - (-1, -10)
Все повороты будут против часовой стрелки, но прямая никак не сможет повернуться больше чем на 90 градусов.
Я бы делал так:
берётся произвольная точка (А), расположенная левее всех точек множества , все остальные(Б) сортируются по углу наклона прямой АБ, после чего проводится прямая через А и среднюю из отсортированных точек. В случае если какие-то ещё точки попадают на эту прямую точку А нужно чуть-чуть сдвинуть.
Алгоритм сложности O(N*log(N)).
А что если соорудить для точек баундинг-бокс (т.е. просто определить крайние координаты), задать точку вне и из нее провести угол, охватывающий все точки. после чего делить его пополам. Если при таком делении заново пересчитывать все точки, то алгоритм также получится O(N*log(N)), но достаточно учитывать лишь точки, попадающие внутрь делимого угла, т.о. сложность будет еще ниже (вроде бы даже O(N)).
А что если соорудить для точек баундинг-бокс (т.е. просто определить крайние координаты), задать точку вне и из нее провести угол, охватывающий все точки. после чего делить его пополам. Если при таком делении заново пересчитывать все точки, то алгоритм также получится O(N*log(N)), но достаточно учитывать лишь точки, попадающие внутрь делимого угла, т.о. сложность будет еще ниже (вроде бы даже O(N)).
спасибо за идеи! сегодня буду что-нить пробывать! если будет проблемы, отпишу... но идеи еще можете скидывать :)))