Как ускорить алгоритм?

Question

[Yura Khlyan]

Доброе время суток.
У меня вот такая задача: дано две точки А(х1, х2) и В(у1, у2), они соединены с началом координат О(0,0) и между собой образуя треугольник АВО. Нужно найти сколько будет таких прямоугольных треугольников удовлетворяющих условию: 0 <= x1, x2, y1, y2 <= N
Вот что у меня вышло, но мне за это стыдно(

def prod(A, B):
    return A[0]*B[0] + A[1]*B[1]

def check_triangle(x1, x2, y1, y2):
    OX = (x1, x2)
    OY = (y1, y2)
    XY = (y1 - x1, y2 - x2)
    sides = sorted([prod(OX, OX), prod(OY, OY), prod(XY,XY)], reverse = True)
    if sides[0]  ==  sides[1] + sides[2] and not 0 in sides:
        return sides

n = int(input()) + 1

def right_triangles(n):
    triangles = [[x1, x2, y1, y2] for x1 in range(n) for x2 in range(n) for y1 in range(n) for y2 in range(n) if check_triangle(x1, x2, y1, y2)]
    return len(triangles) // 2                  

print (right_triangles(n))

Есть идеи как сделать это быстрее? Буду очень благодарен за помощь.

UPD. Координаты целые числа

Comments

[vaut]

В условии вероятно не добавлено что координаты точек целые.

Answer 1

[Mrrl]

Сначала учитываем 3*N^2 треугольников, у которых вершина с прямым углом лежит на одной из координатных осей (или вообще в точке (0,0)).
Теперь посчитаем все остальные треугольники.
Пусть (a,b) - координаты вершины с прямым углом, 0 < a <= N, 0 < b <= N.
Если c=НОД(a,b), a1=a/c, b1=b/c, то оставшаяся вершина должна иметь координаты (x,y)=(a+t*b1,b-t*a1), где t - ненулевое целое число.
Должны выполняться условия 0 <= x,y <= N. Перепишем их в виде условий на t:
-a/b1 <= t <= (N-a)/b1, -(N-b)/a1 <= t <= b/a1 (заметим, что a1, b1 больше нуля, так что делить можно). Учитывая, что t должно быть целым, оно лежит на отрезке от
t0 = -floor(min(a/b1,(N-b)/a1))
до
t1 = floor(min((N-a)/b1,b/a1))
И, поскольку запрещённое значение 0 всегда принадлежит этому отрезку, получаем, что число треугольников с вершиной (a,b) равно t1-t0.
Перебираем все точки (a,b), считаем t1-t0 и суммируем.
Всё. Сложность N^2*log(N), основное время тратится на вычисление НОД.
Если надо быстрее - надо будет думать. Скорее всего, надо будет перебирать взаимно простые пары (a1,b1), считать, сколько точек попало в перекошенный квадрат (переведённый в базис (a1,b1), (-b1,a1)), искать для них формулу и суммировать. Может быть, получится, может быть, нет. Какого порядка N?

Answer 2

[Antony]

Я так понял вы просто перебираете все возможные варианты (питона я, увы, не знаю). Составте систему уравнений и сделайте ее решение в общем виде и туда уже подставляйте исходные данные. Это будет быстрее.

Ну и, если что, кординаты точек будут правильнее выглядеть вот так: А(х1, y1) и В(x2, у2).

Кроме того у вас в задании ошибка. Я правильно понимаю, что x1, x2, y1, y2 - должны быть целыми числами (в противном случае задача имеет бесконечно большое колличество решений).

Comments

[Yura Khlyan]

Antony :
Я что-то не могу понять какого типа систему уравнений составить?

Answer 3

[vaut]

Есть вот какие мысли по оптимизации:
1) проверять прямой угол в точке с помощью скалярного произведения.
(Ax*Bx+Ay*By)/|a|+|b| = 1
2) проверять не на соответствие прямоугольника а только угол в первой точке.
3) проверять на прямой угол только вершины находящиеся под прямой x=y, и результат умножить на 2. Только нужно осторожно обработать случаи когда прямой угол лежит на ней.
4) В качестве второй точки перебирать не все точки а только те которые находятся внутри квадрата описанного вокруг окружности с центром в между (0,0) и нашей точкой, и снаружи вписанного в ту же окружность.
5) Можно просто по этой окружности идти: увеличиваем x, проверяем целый ли y. Нам даже не придется проверять угол на прямой.

Питона я не знаю, по этому не вижу где в примере делится на 2. Иначе каждый треугольник становится посчитан два раза.

Answer 4

[SilentFl]

Если надо найти количество прямоугольных треугольников с прямым углом в начале координат, то можно применить такой трюк: отсортировать точки в соответствии с их углом до оси OX, далее запускаем цикл, фиксируя текущую точку A[i], а вторую B (т.е. третью вершину треугольника) - ищем бинарным поиском, зная что ее угол до OX есть угол A[i]+90 градусов. Сложность снижается с ваших O(n^2) до O(nlogn).
Если треугольники считаются нужными если могут иметь прямой угол 0AB или 0BA, то ничего быстрее перебора не придумать, имхо

Comments

[vaut]

Со всеми положительными координатами и прямым углом в начале координат 0 треугольников :)
Я лучше O((n^3)/2) не могу придумать против авторских O(n^4).

[Yura Khlyan]

vaut, SilentFl:
Угол может быть не только в начале. Например О(0,0), А(0,2), В(1,1)

[SilentFl]

таки вторая часть. пробуем сделать из нее первую: точка 0,0 - точно такая же точка; цикл по i - фиксация "нулевой точки", сортируем относительно угла ох, цикл по j - перебор оставшихся точек и поиск к ним третьей вершины за logn. далее переходим на следующую по i вершину, снова делаем ее нулевой и процесс повторяем. Сложность O(N^2*logN). Ы?