// ////////////////////////////////////////////////////////
// # Title
// Right triangles with integer coordinates
//
// # URL
// https://projecteuler.net/problem=91
// http://euler.stephan-brumme.com/91/
//
// # Problem
// The points `P(x1,y1)` and `Q(x2,y2)` are plotted at integer co-ordinates and are joined to the origin, `O(0,0)`, to form a triangle `\triangle OPQ`.
//
// ![coordinate system](p091_1.gif)
//
// There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive;
// that is, `0 <= x1, y1, x2, y2 <= 2`.
//
// ![coordinate system](p091_2.gif)
//
// Given that `0 <= x1, y1, x2, y2 <= 50`, how many right triangles can be formed?
//
// # Solved by
// Stephan Brumme
// March 2017
//
// # Algorithm
// The location of `O` was fixed at `(0,0)` but `P` and `Q` can be anywhere (but `O!=P!=Q`).
// To simplify my algorithm I define that the right angle is always at `O` or `P` and never at `Q`.
// The size of the grid is 50x50, each side has length `size=50`.
//
// I identified 4 cases:
// 1. The right angle is at the origin `O`. `P` and `Q` can be anywhere on the x-/y-axis:
// `P(0 that's `size^2` different triangles.
//
// 2. The right angle is on the x-axis at `P(0 that's `size^2` different triangles.
//
// 3. The right angle is on the y-axis at `P(0, 0 that's `size^2` different triangles.
//
// 4. The right angle is "inside" the grid at `P(0 0)
// until any coordinate leaves the grid. The same procedure is done with inverse sign for k < 0.
//
// A simple speed-up was achieved by observing that the number of valid `Q` is the same for `P(p_x, p_y)` and `P(p_y, p_x)`.
// That means that the two nested loops only need to considered the bottom-right triangle of the grid: `P(p_x, p_y<=p_x)`.
// For `P(p_x, p_y
#include
// greatest common divisor
unsigned int gcd(unsigned int a, unsigned int b)
{
while (a != 0)
{
unsigned int c = a;
a = b % a;
b = c;
}
return b;
}
int main()
{
unsigned int size = 50;
std::cin >> size;
// triangles where right angle is in the origin
unsigned int result = size*size;
// plus triangles where the right angle is located on the x-axis
result += size*size;
// plus triangles where the right angle is located on the y-axis
result += size*size;
// now all triangles where the right angle at point P(x > 0, y <= x)
// that's the triangle in the bottom-right half, denoted by slashes
// ^ /
// | //
// | ///
// |////
// +--->
for (unsigned int p_x = 1; p_x <= size; p_x++)
for (unsigned int p_y = 1; p_y <= p_x; p_y++)
{
// reduce to a proper fraction
unsigned int factor = gcd(p_x, p_y);
unsigned int deltaX = p_x / factor;
unsigned int deltaY = p_y / factor;
unsigned int found = 0;
// assume Q is "below" P
int q_x = p_x - deltaY;
int q_y = p_y + deltaX;
while (q_x >= 0 && q_y <= (int)size)
{
found++;
q_x -= deltaY;
q_y += deltaX;
}
// assume Q is "above" P
q_x = p_x + deltaY;
q_y = p_y - deltaX;
while (q_y >= 0 && q_x <= (int)size)
{
found++;
q_x += deltaY;
q_y -= deltaX;
}
// mirror along y=x when p_y < p_x
if (p_x != p_y)
found *= 2;
result += found;
}
std::cout << result << std::endl;
return 0;
}