Консультация № 110207
19.11.2007, 23:06
0.00 руб.
0 1 1
Здравствуйте эксперты! Помогите пожалуйста написать такую программу:
Найти четырехугольник с вершинами в заданных точках, содержащий наибольшее число заданных точек.

Обсуждение

Неизвестный
20.11.2007, 10:34
общий
это ответ
Здравствуйте, Maniak_8989!
Могу предложить такой метод решения: перебором берете 4 точки и с помощью уравнения из геометрии проверяете, с какой стороны отрезка (из 2 выбранных точек) находятся все остальные точки.
Так как это может быть очень грузным способом, можно отсортировать точки по Х и по У. Ведь в принципе самое большое количество будет охватывать самый наружный 4-угольник. Конечно, есть исключение, поэтому лучше перебирать все ))) если это не критический код...
Отсортироваав список по координатам, можно увеличить скорость определения принадлежности точки к 4-угольнику - по индексам массива....
Форма ответа