![]() |
|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
||||
|
||||
![]() Всем доброго...
Имеется задача: есть массив данных вида A[0..N,0..3]: array of single; массив содержит максимум 10000 элементов (N<=10000), элементы представляют собой координаты начала и конца отрезков, т.е. A[0,0]:=X1; A[0,1]:=Y1; A[0,2]:=X2; A[0,3]:=Y2; ... A[N,0]:=Xn+1; A[N,1]:=Yn+1; A[N,2]:=Xn+1; A[N,3]:=Yn+1; Вопрос заключается в следующем: как найти номера отрезков, которые в своей совокупности составляют замкнутую фигуру, причем отрезки, составляющие эту фигуру, могут идти в массиве не друг за другом и не обязательно X1 и Y1 cоответствуют началу отрезка (X1 и Y1 может быть концом отрезка), при этом доподлинно известно, что замкнутая фигура состоит максимум из четырех отрезков. Вот такая вот задача. По теории графов (с коей я не особо хорошо знаком) накидал алгоритм, который сводиться к почти тупому перебору, но в этом случае, если N примет свое максимальное значение, то перебор затянется надолго, у кого есть какие мысли на этот счет? может представлять данные не массивом, а вогнать в базу данных? или еще есть какой-то вариант? З.Ы. (для понимания определений, используемых в вопросе) считается, что фигура замкнутая, если конец одного отрезка, ее составляющего, является началом другого отрезка, также составляющего эту фигуру и конец последнего отрезка этой фигуры является началом первого отрезка этой фигуры, в данном случае таких отрезков может быть максимум четыре, т.е. фигура может быть, например, квадратом, прямоугольником, трапецией или треугольником Понять, что хочет заказчик - бесценно, ведь он платит MasterCard ![]() |