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

Сначала учитываем 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?

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

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

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

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

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

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