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

← →
shkolnik (2015-10-17 01:35) [0]

Я не прошу написать задачу, прошу подсказать алгоритм.
Есть N координат точек на плоскости.
Необходимо найти кол. квадратов, которые образуют точки.

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

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

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

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

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

спасибо.

← →
ВладОшин © (2015-10-17 11:47) [1]

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 проверять были ли эти точки уже проверены, если они в другом порядке уже приходили

← →
shkolnik (2015-10-17 15:52) [2]

спасибо ВладОшин, но тут полный перебор идет.
>> можно перед Check проверять были ли эти точки уже проверены
дополнительно массив заводить на проверенные комбинации - как-то оно не красиво.

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

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

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

Задача по программированию Найти похожие ветки