Найти количество конгруэнтных треугольников?

Question

Say I have a square from (0,0) to (z,z). 
Given a triangle within this square which has integer coordinates 
for all its vertices.
Find out the number of  triangles within this square which are 
congruent to this triangle and have integer coordinates. 
My algorithm is as follows--


 1) Find out the minimum bounding rectangle(MBR) for the given triangle.
 2) Find out the number of congruent triangles, y within that MBR,
    obtained after reflection, rotation of the given triangle. 
    y can be either 2,4 or 8.
 3) Now find out how many such MBR's can be drawn within the given 
    big square, say x;
    (This is similar to finding number of squares on a chess board)
 4) x*y is the required answer.

Считаю ли я некоторые треугольники более одного раза или что-то упускаю по этому алгоритму? Это проблема онлайн судьи? Это дает мне неправильный ответ. Я много об этом думал, но не могу понять.

Answer 1

Подход, который вы описываете, довольно близок, но не учитывает все конгруэнтные треугольники в сетке.

Самое существенное упущение связано с тем, что есть повороты которые сохраняют целочисленные координаты, но не кратны 90 градусам.

Рассмотрим треугольник с вершинами (0,0), (240,0) и (240,180). Повернуть его против часовой стрелки относительно начала координат арксинусом (3/5), или приблизительно 37 градусов, чтобы получить конгруэнтный треугольник с вершинами (0,0), (192,144), и (84 288).

Ограничительная рамка для нового треугольника имеет другое соотношение сторон, чем оригинал, который также вводит некоторые трудности.

Вот алгоритм, который, учитывая три точки на сетке NxN, должен перечислять все конгруэнтные треугольники в O (N ³ ) времени.

Пусть P = (x, y) обозначает точку с целочисленными координатами, а

T (p, q, r) треугольник, образованный из различных точек p, q и r.

T (q, r, p), T (r, p, q), T (p, r, q) обозначают один и тот же треугольник, поэтому рассмотрим треугольник с

p будет его каноническим представлением.

Мы можем определить p ((p.y Два треугольника T1 = (A, B, C) и T2 = (P, Q, R), причем оба T1 и T2 в каноническом формы, совпадают, если:

|AB| = |PQ|,
|BC| = |QR|, and 
|CA| = |RP|.

Чтобы избежать сравнений с плавающей запятой, мы можем сравнить квадраты длина.

Рассмотрим отрезок AB с A в начале координат (0,0), A 2 = L.

(Обратите внимание, что sqrt (L) равно O (N), так как каждая сторона треугольник должен вписываться в сетку NxN с максимальной диагональю sqrt (2) * N).

Мы можем найти возможные выбор B, проверяя все точки (x, y) в треугольнике определяется

(0,0), 
(0,ceil(sqrt(L)), and 
(ceil(sqrt(L), ceil(sqrt(L))

Это требует вычисления | AB | ² для точек O (N ² ), затем применяя симметрию, чтобы получить до 4 баллов за каждый матч найдено в области поиска:

Если B = (x, y) имеет x = 0, дополнительных точек нет, так как (0, -y) <(0, y), что нарушает условие </p>

A Если x = y с x> 0, A <(-x, y) и т. Д. (-X, y) является допустимым выбором для Б. </p> Если y 0, точки (y, x), (-x, y) и (-y, x) все удовлетворить условия.

Хотя мы искали O (N ² ) точек, самое большее O (N) будет иметь правильную длину. (Они все будут лежать на круге радиуса sqrt (L) и окружности 2 * pi * sqrt (L) от начала координат, и будут отделены как минимум одним блоком друг от друга.)

Эта процедура находит все возможные ориентации отрезка AB, с A 2 = L. Сохраните этот список точек B, затем используйте ту же процедуру для создания списков точек для значений L соответствует двум другим сторонам треугольника прототипа.

Теперь мы хотим построить набор треугольников (A, B, C) с фиксированным A на происхождение, и B выбран из списка точек из списка, который мы сделали для длина | AB |. C можно определить за время O (1), найдя точки пересечения из двух окружностей , один из которых центрирован на A с радиусом | AC |, а другой - на B с радиусом | BC |. (Этот шаг легче всего выполнить, решив круг пересечение в плавающей точке, затем брать ближайшие точки решетки к плавающей точечные решения. Точки решетки можно подтвердить с помощью целочисленной математики, а затем проверить, удовлетворяет ли какая-либо из них ограничению. A Учитывая, что каждый (A, B, C) отличается от прототипа только поворотом из набора размера O (N) и симметрии из набора размером O (1), мы получаем список треугольников длины O (N).

В зависимости от того, является ли треугольник прототипа равносторонним, равнобедренным,или разносторонне, нам нужно будет рассмотреть 1, 3 или 6 перестановок длины сторон, чтобы найти все треугольники (A, B, C), совпадающие с прототип, с A На этом этапе некоторые треугольники в списке могут не соответствовать сетка (возможно, потому что одна сторона имела длину, близкую к sqrt (2) * N и должен быть под углом к ​​оси X). Для равнобедренных и равносторонних треугольники, в зависимости от деталей алгоритма поиска, некоторые из треугольники могут появляться более одного раза, а вершины избыточных треугольников выходят из строя. Они могут быть удалены из списка, снова в O (N) время. Финальный список треугольников представляет полный набор конгруэнтных треугольников с A, зафиксированным в начале координат, удовлетворяющий всем условиям мы наложили, и это набор размера O (N).

Наконец, мы позволяем точке А отойти от начала координат до некоторой другой точка сетки. Есть O (N ² ) вариантов для A, и для каждого Выбрав A = (x, y), мы составим список из O (N) переведенных треугольников, добавив координаты (x, y) для каждого из A, B и C из списка «происхождение». Мы проверяем в O (1) время, чтобы убедиться, что каждый из переведенных A, B, C точки все еще находятся в сетке NxN, а те, которые выживают, получают добавлен в окончательный список вывода. Время выполнения этого шага O (N ³ ), и это доминирует во время выполнения всего алгоритм поиска.

Используя приведенный выше пример на сетке 289x289, наш прототип треугольник имеет координаты A = (0,0), B = (240,0) и C = (240,180). Пусть Z равно началу координат (0,0).

| AB | ² - 57600. | BC | ² составляет 32400. | CA | ² составляет 90000.

Из первой части алгоритма точки B с L = r ² = 57600 от Z и Z (0, 240), (240, 0), (144, 192), (192, 144), (-144, 192), (-192, 144)

Точки C с L = 32400 и Z

(0, 180), (180, 0), (108, 144), (144, 108), (-108, 144), (-144, 108)

Точки A с L = 90000 и Z

(84, 288), (288, 84), (-84, 288), (-288, 84), (180, 240), (240, 180), (-180, 240), (-240, 180)

Треугольники, полученные из этих наборов координат, после принимая все 6 перестановок длин сторон и обрезая те, которые не соответствуют условиям, являются:

(0, 0),(-180, 240),(0, 240)   L= 90000 32400 57600
(0, 0),(0, 240),(180, 240)    L= 57600 32400 90000
(0, 0),(240, 0),(240, 180)    L= 57600 32400 90000
(0, 0),(192, 144),(84, 288)   L= 57600 32400 90000
(0, 0),(-192, 144),(-84, 288) L= 57600 32400 90000
(0, 0),(240, 0),(0, 180)      L= 57600 90000 32400
(0, 0),(0, 180),(240, 180)    L= 32400 57600 90000
(0, 0),(180, 0),(180, 240)    L= 32400 57600 90000
(0, 0),(108, 144),(-84, 288)  L= 32400 57600 90000
(0, 0),(-108, 144),(84, 288)  L= 32400 57600 90000
(0, 0),(180, 0),(0, 240)      L= 32400 90000 57600
(0, 0),(144, 108),(-144, 192) L= 32400 90000 57600
(0, 0),(-144, 108),(144, 192) L= 32400 90000 57600
(0, 0),(-240, 180),(0, 180)   L= 90000 57600 32400
(0, 0),(288, 84),(144, 192)   L= 90000 32400 57600
(0, 0),(-288, 84),(-144, 192) L= 90000 32400 57600
(0, 0),(-180, 240),(0, 240)   L= 90000 32400 57600

Перевод их в сетку 289x289 и обрезка те, которые не подходят, мы получаем окончательный список из 43 504 треугольников.

Первые несколько:

(0, 0),(0, 240),(180, 240)  L= 57600 32400 90000
(0, 0),(240, 0),(240, 180)  L= 57600 32400 90000
(0, 0),(192, 144),(84, 288) L= 57600 32400 90000
(0, 0),(240, 0),(0, 180)    L= 57600 90000 32400
(0, 0),(0, 180),(240, 180)  L= 32400 57600 90000
(0, 0),(180, 0),(180, 240)  L= 32400 57600 90000
(0, 0),(180, 0),(0, 240)    L= 32400 90000 57600
(0, 0),(288, 84),(144, 192) L= 90000 32400 57600
(0, 1),(0, 241),(180, 241)  L= 57600 32400 90000
(0, 1),(240, 1),(240, 181)  L= 57600 32400 90000
(0, 1),(240, 1),(0, 181)    L= 57600 90000 32400

и последние несколько:

(288, 94),(0, 178),(144, 286)  L= 90000 32400 57600
(288, 95),(48, 275),(288, 275) L= 90000 57600 32400
(288, 95),(0, 179),(144, 287)  L= 90000 32400 57600
(288, 96),(48, 276),(288, 276) L= 90000 57600 32400
(288, 96),(0, 180),(144, 288)  L= 90000 32400 57600
(288, 97),(48, 277),(288, 277) L= 90000 57600 32400
(288, 98),(48, 278),(288, 278) L= 90000 57600 32400
(288, 99),(48, 279),(288, 279) L= 90000 57600 32400
(288, 100),(48, 280),(288, 280) L= 90000 57600 32400
(288, 101),(48, 281),(288, 281) L= 90000 57600 32400
(288, 102),(48, 282),(288, 282) L= 90000 57600 32400
(288, 103),(48, 283),(288, 283) L= 90000 57600 32400
(288, 104),(48, 284),(288, 284) L= 90000 57600 32400
(288, 105),(48, 285),(288, 285) L= 90000 57600 32400
(288, 106),(48, 286),(288, 286) L= 90000 57600 32400
(288, 107),(48, 287),(288, 287) L= 90000 57600 32400
(288, 108),(48, 288),(288, 288) L= 90000 57600 32400

Время выполнения не превышало одной секунды для генерации этого списка для сетки 289x289.

Answer 2

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

Вместо этого назначьте одну из точек примера треугольника в качестве начала координат. Попробуйте все точки решетки окружности радиуса первой стороны как места для второй вершины. После того, как вы выбрали точку-кандидат, вычислите местоположение третьей вершины и, если это тоже точка решетки, то рассчитайте, сколько раз результирующий треугольник вписывается в квадрат без поворота. Единственная симметрия, о которой вам нужно беспокоиться - это если исходный треугольник равнобедренный или равносторонний, что приведет к тому, что вы будете пересчитывать треугольники в 2 и 3 раза соответственно.

Answer 3

Хотите знать точное количество треугольников справедливой оценки?

Для «точного» ответа у меня нет, но я уверен, что использование MBR для этого не очень хорошая идея, потому что:

1. могут быть треугольники, которые пересекают границы MBR
2. могут быть треугольники с целочисленными координатами с масштабом, не равным целому числу (т. Е. Через вращение. Это теория (потому что у меня нет примера в руках), но мы должны доказать, что это неправильно, прежде чем идти вперед)

Если вы хотите узнать оценку, чем MBR достаточно хорош