Проблема со связанными точками и определение геометрических фигур на основе анализа местоположения точек

Question

В школе у ​​нас действительно тяжелая проблема, и до сих пор никто из учеников ее не решил. Посмотрите на картинку ниже:

http://d.imagehost.org/0422/mreza.gif

Это своего рода сеть связанных точек, которая не заканчивается, и каждая точка имеет свой собственный номер, представляющий ее. Допустим, числа такие: 1-23-456-78910-и т. Д. и т. д. (Вы не можете видеть числа 5 или 8,9 ... на картинке, но они есть, и их положение очевидно, точка в середине 4 и 6 - 5 и т. д.).

1 подключен к 2 и 3, 2 подключен к 1,3,5 и 4 и т. Д.

Цифры 1-2-3 указывают на то, что они представляют треугольник на рисунке, а цифры 1-4-6 - нет, потому что 4 напрямую не связано с 6.

Давайте посмотрим на 2-3-4-5, это параллелограмм (вы знаете почему), но 4-6-7-9 НЕ параллелограмм, потому что в этой задаче есть правило, которое говорит, что все стороны должны быть равны для всех фигур - треугольников и параллелограммов.

Также есть шестиугольники, например. 4-5-7-9-13-12 - это шестиугольник - и здесь все стороны должны быть равны.

12345 - это ничего не представляет, поэтому мы игнорируем это.

Думаю, я хорошо объяснил проблему. Актуальная проблема, которая задается нам с помощью ввода чисел, как указано выше, чтобы определить, является ли это треугольником / параллелограммом / шестиугольником (согласно описанным правилам).

Например:

1 2 3 - triangle
11 13 24 26 -parallelogram
1 2 3 4 5 - nothing
11 23 13 25 - nothing
3 2 5 - triangle

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

Если у вас есть какие-либо идеи о том, как решить эту проблему, ответьте, вы можете использовать псевдокод или C ++, что угодно. Большое спасибо.

Answer 1

Давайте упорядочим точки следующим образом:

1
2  3
4  5  6
7  8  9  10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28

Вы можете сохранить это в матрице. Теперь пусть row[i] = the row number i is on и col[i] = the column number i is on. Они могут быть вычислены более или менее эффективно для каждого i.

Сначала отсортируйте данные по возрастанию. Вам понадобится ровно 3 очка для треугольника, 4 для параллелограмма и 6 для шестиугольника - все остальное, и вы можете отклонить его как не цифру.

Обратите внимание, что в этой матрице мы можем иметь только прямоугольные треугольники в соответствии с вашими правилами. Маркируйте три точки A, B, C. Вы можете проверить, образуют ли они треугольник, итерируя от row[A] до row[B], затем от col[B] до col[C], а затем по диагонали от row[C] до row[A] и проверяя, совпадают ли расстояния, и если вы доберетесь до нужных позиций. Вы можете прекратить это так рано, например, если B равно 8, а A равно 1, то вы можете сказать, что не найдете его, как только нажмете 11 в столбце 1.

Для параллелограммов аналогичные рассуждения могут быть сделаны. Пометьте 4 точки A, B, C, D и не забудьте отсортировать их по возрастанию (помните, что ваши точки здесь на самом деле числа). Посмотрите, можете ли вы получить от col[A] до col[B] на той же строке, затем от col[C] до col[D] на той же строке и затем по диагонали или по вертикали вниз с row[A] до row[C], а затем (в в том же направлении вы пошли на предыдущую диагональ!) ​​от row[B] до row[D].

Шестиугольники также имеют определенный формат, который вы должны проверить. Вот как выглядят шестиугольники в этом представлении:

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36

Вы можете заметить, что каждые две пары точек имеют один и тот же столбец и что горизонтальное расстояние между двумя средними точками вдвое больше вертикального расстояния между любыми двумя точками, а также вдвое больше горизонтального расстояния между любыми двумя другими точками.

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

Вам даже не нужны массивы row и col, если вы не планируете эффективно их вычислять. Просто пройдитесь по матрице, пока не определите первую точку в отсортированном порядке, и попробуйте добраться до других, следуя каждому из правил.

Не совсем хороший способ, но для этого вам понадобится только матрица 256x256, поэтому, хотя это приводит к довольно большому количеству кода, он довольно эффективен. Я надеюсь, что я дал понять, если нет, пожалуйста, скажите, что не ясно. В любом случае, может быть, кто-то еще опубликует лучшее решение, так что подождите немного, если сможете ..