Maximum Triangle Area

Problem MaxTriangle SRM 449 Div-1 250 pts problem.

Here is the problem description:

A triangle with positive area has been positioned on the plane in such a way that all of its vertices are located at integer coordinates. The lengths of two sides of this triangle are equal to sqrt(A) and sqrt(B), where sqrt(X) denotes the squared root of X. Return the maximum area this triangle can have. If there is no such triangle, return -1 instead.

Solution to this problem:

We can use vectors to solve such kinds of problems, the input is the squared of magnitude of two vectors, so we need to get all vectors that can give a magnitude value equals to sqrt(A) and sqrt(B).

Given that magnitude of a two dimensional vector(x, y) can be computed using the following equation:

Magnitude = sqrt(x*x+y*y)

So we need to iterate all valid x and y that can evaluates to this x*x+y*y=c, where c equals the squared magnitude passed.

The following method takes a squared magnitude as a parameter and returns the list of vectors:

Note: For each valid x and y, the following are also valid as per the above equation (x, y), (-x, y), (x, -y), (-x, -y).

Now we can iterate for all pairs of vectors of both squared magnitudes A and B, to get the maximum area of a triangle. To compute the area of a triangle between two two dimensional vectors is done using cross product.

See the following video but this is for three dimensional vectors.

Cross product of two dimension vectors (x1, y1) and (x2, y2) = x1*y2-x2*y1

Read this.

Here is my code for this problem.