Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Задача по программированию

shkolnik © (2015-10-17 01:35:00)
Я не прошу написать задачу, прошу подсказать алгоритм.
Есть N координат точек на плоскости.
Необходимо найти кол. квадратов, которые образуют точки.

Планирую делать так:

1. функция, принимает 4 координаты и проверяет образуют они квадрат или нет.
планирую проверять по парам по общему X и между ними пары должны иметь общую по Y. так же можно вероятно проверять расстояния между точками что бы было равно ну и угол 90 градусов или равные диагонали.

2. нужно выбирать из общего кол. координат по 4 варианта и передавать в функцию поиска квадрата между ними.
как понимаю кол. вариантов это n!\4! * (n-4)!

вот тут и проблема с алгоритмом, - как-то в голове не складывается вариант перебора массива элементов по всем возможным комбинациям по 4.

может подскажите? ну или может какие мысли будут другие для решения этой задачи.

спасибо.

shkolnik (2015-10-17 15:52:00) [1]
спасибо ВладОшин, но тут полный перебор идет.
>> можно перед Check проверять были ли эти точки уже проверены
дополнительно массив заводить на проверенные комбинации - как-то оно не красиво.

думаю завести 4 указателя на массив координат.

главный цикл перебираем первый указатель с 1 до n - 3
второй цикл перебирает указатель с 2 до n-2
третий цикл перебирает указатель с 3 до n-1
четвертый цикл перебирает указатель с 4 до n
в котором и вызывается проверка 4 координат по указателям этим на массив

думаю тут как раз будет одноразовая проверка.

ВладОшин (2015-10-17 11:47:00) [2]
p = record x,y integer end
N array of p
for i1 1 - N
for i2 1 - N
for i3 1 - N
for i4 1 - N
Check(N[i1],N[i2],N[i3],N[i4],)

можно перед Check проверять были ли эти точки уже проверены, если они в другом порядке уже приходили

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »