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