Find the total number of interior points having integral co-ordinates that lie inside the triangle having vertices as and
Bonus: Can you generalize it for a triangle having vertices as and
Try also Integral Co-ordinates--2 .
Try also Integral Co-ordinates .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Lets take yhe vertices as P ( α 1 , α 2 ) , Q ( β 1 , β 2 ) and R ( γ 1 , γ 2 )
Let L 1 be the line joining P and Q , L 2 be line joining Q and R and L 3 be line joining P and R
Hence, L 1 → β 1 − α 1 x − α 1 = β 2 − α 2 y − α 2
L 2 → γ 1 − β 1 x − β 1 = γ 2 − β 2 y − β 2
And L 3 → γ 1 − α 1 x − γ 1 = γ 2 − α 2 y − γ 2
Using Pick's Theorem , Area of Polygon, A = I + 2 B − 1
Where, I is number of points on the interior of the polygon
B is the number of points on the boundary of the polygon.
B = Number of points on the lines L 1 , L 2 and L 3 including end points
= g c d ( β 2 − α 2 , β 1 − α 1 ) − 1 + g c d ( γ 2 − β 2 , γ 1 − β 1 ) − 1 + g c d ( γ 2 − α 2 , γ 1 − α 1 ) − 1 + 3 P , Q , R
Area of Triangle is given by A ′ = 2 1 ∣ ∣ ∣ ∣ ∣ ∣ α 1 β 1 γ 1 α 2 β 2 γ 2 1 1 1 ∣ ∣ ∣ ∣ ∣ ∣
Now, A = A ′
N = I = 2 1 ∣ ∣ ∣ ∣ ∣ ∣ α 1 β 1 γ 1 α 2 β 2 γ 2 1 1 1 ∣ ∣ ∣ ∣ ∣ ∣ − 2 1 ( g c d ( β 2 − α 2 , β 1 − α 1 ) + g c d ( γ 2 − β 2 , γ 1 − β 1 ) + g c d ( γ 2 − α 2 , γ 1 − α 1 ) ) + 1
Now, for our Coordinates input in the above formula to get N = 3