@MAGistr_MTM
Учусь программировать

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

Доброе время суток.
У меня вот такая задача: дано две точки А(х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. Координаты целые числа
  • Вопрос задан
  • 761 просмотр
Пригласить эксперта
Ответы на вопрос 4
Mrrl
@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?
Ответ написан
RiseOfDeath
@RiseOfDeath
Диванный эксперт.
Я так понял вы просто перебираете все возможные варианты (питона я, увы, не знаю). Составте систему уравнений и сделайте ее решение в общем виде и туда уже подставляйте исходные данные. Это будет быстрее.

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы