How to solve codechef TRIANLUV?

general
, ,
1

Please explain the approach and solution for this problem.

https://www.codechef.com/problems/TRIANLUV

Thanks.

2

The first thing to do is identify how many integer-coordinate points there are on each side of the triangle. Then identify different ways to select points from those sets to make a non-degenerate triangle.

How many integer-coordinate points:
Looking at one side AB, the X- and Y-coordinates change by a certain amount from A to B - say 40 and 12. Then any point on that side with integer coordinates changes X and Y from A in the same ratio - for example 20 and 6. So there will be 3 internal points along that side, changing by (10,3), (20,6) and (30,9). Reducing from (40,12) to the first (10,3) involves dividing by the GCD of 40 and 12, GCD(40,12) = 4. Including one of the end points, say B, this gives us exactly that the GCD of the coordinates of each side difference gives us the number of integer coordinates on the triangle.

3

Yes, but how to compute the numbet of integer-coordinate points on each side?

4

OK, added a sketch of how to do that