You live a simple and happy life in your farm.
You grow all sorts of vegetables in the fields.
Some days of the year, you toil the soil all day planting carrots, tomatoes, lettuce, cabbage, beet, pepper and many others.
At night you are so tired that you sleep deeply and without any dreams.
The rains come and the fields become a deep luxuriant green with spots of red, yellow, orange, purple and patches of mint green.
One day while harvesting that season's carrots, you sit midday on a rock for a brief respite. Lines and lines of carrots extend in every direction.
The sun shines strongly above. You are thirsty and tired. Suddenly you see some leaves move slightly. As in a dream (perhaps you did indeed take a nap?) you see a neatly dressed carrot man approach you.
"Good day sir" says the carrot man. After a short pause as if expecting you to say something he continues "we see you working all day pulling our neighbors from the soil and we ask each other how long before we too will be taken from our homes?".
"I have never thought of it that way. I don't even know how many of you there are?" you mumble a bit embarrassed.
"There is a very simple way to estimate that sir. Imagine that there is one carrot being living at each integer set of coordinates (x,y) of this field.. Then you certainly can figure out how many carrots lie in the line between any two carrots at coordinates (x1,y1) and (x2,y2)? If you then extend your reasoning to find how many carrots are in a rectangle that has its diagonal given by the same line segment you can find out how many of us there are."
Having completed this discourse the carrot man turned and slowly walked to the neighboring row of carrots, past it and soon he had disappeared among the greenery.
After this conversation you hesitate going back to your carrot pulling task. You try to solve the problem posed by the carrot man instead. How many carrots there are in the line segment between two carrots? And how many carrots lie in a rectangle whose diagonal is given by the same line segment?
Consider all carrots that lie inside (but not on the border) of a rectangle where the lower left corner is at coordinates min(x1,x2), min(y1,y2) and the top right corner is at coordinates max(x1,x2),max(y1,y2).
We can check for each of these carrots whether they lie or not in the segment connecting (x1,y1) to (x2,y2). How?
Form the vector that joins the two ends of the segment. Its components will be (max(x1,x2)-min(x1,x2), max(y1,y2)-min(y1,y2)).
Then form the vector connecting the lower left corner of the rectangle at (min(x1,x2),min(y1,y2)) to the point inside the rectangle at integer coordinates (i,j).
This vector has coordinates (i-min(x1,x2)),j-min(y1,y2)).
The point lies on the segment when the angle between these 2 vectors is zero.
The cross product of these two vectors is the product of their magnitudes times the sin of the angle between them. Therefore the cross product will vanish if these two vectors are collinear, i.e. if the point lies on the segment.
The cross product is a vector parallel to the z axis (the axis perpendicular to the field where the carrots lay) with value
All points inside the rectangle for which this difference is zero, are on the line segment.
Without loss of generality we can always put the lower left corner of the rectangle at the origin of the coordinates (0,0) and the top right corner at the point (x2-x1,y2-y1) (assuming x2>x1 and y2>y1). The rectangle has sides of length (x2-x1) and (y2-y1).
All integer points on this segment must obey the line equation y=(y2-y1)/(x2-x1)x. Or y/x=(y2-y1)/(x2-x1).
Lets suppose that the GCD of (y2-y1) and (x2-x1) is ...GCD. We can write
y = GCD*p/(GCD*q)x
where p and q are relatively prime (coprime), i.e. they have no common divisors.
It is clear then that the following integer points are on the segment: (q,p), (2q,2p), (3q,3p),..., ((GCD-1)x, (GCD-1)y). Therefore there are GCD-1 integer points/carrots in the segment (excluding the endpoints).
For an example consider (x2-x1)=10 and (y2-y1)=15. Then y/x=3*5/(2*5). Pairs (2,3), (4,6), (6,9), (8,12) are all in the segment. The GCD is 5 and there are 4 points on the segment.
This also shows that if (x2-x1) and (y2-y1) are coprimes (i.e. they dont have any common divisors), there can not be any integer point lying on the segment (other than the endpoints).
Put another way dividing the rectangle of size (x2-x1,y2-y1) into the greatest number of identical rectangles is equivalent to finding the greatest common divisor of (x2-x1) and (y2-y1).
How many carrots are inside the rectangle whose diagonal is the segment from (x1,y1) to (x2,y2)?
The easiest way to count those is to count them as we loop through every point of integer coordinates on or inside the rectangle.
But since the problem is so easy we can try to be clever and come up with a formula for this number.
To find out how many carrots are right on the rectangle border we could use the cross product or gcd methods above applied to each of the four sides of the rectangle. Actually the top and bottom sides will have the same number of carrots as will the left and right sides so we can just use two sides and multiply by two.
But it is easier to do things manually:
The bottom side will have (x2-x1)+1 points (because of the origin). Adding the top side this gives
2[x2-x1+1]. The left and right side contribute 2[y2-y1+1]. But 4 of the points are counted twice, so
the total number of carrots on the boundaries of the rectangle is
2[x2-x1+1+y2-y1+1-2]=2(x2-x1+y2-y1)
How many carrots will be inside the rectangle? Divide the rectangle by vertical lines parallel to its left and right sides and starting at integer values of x. There will be (x2-x1)-1 of those lines (excluding the left and right sides). For each of those lines there will (y2-y1)-1 points with integer y coordinates. So there will be a total of [x2-x1-1][y2-y1-1] interior carrots.
The total number of carrots in the rectangle (interior and boundary) is then
(x2-x1)(y2-y1)+ (x2-x1+y2-y1)+1
The following code implements both the cross product and gcd solutions. In particular notice the implementation of gcd using the Euclidean algorithm. The code also counts the number of points inside and on the rectangle and compares it with the formula above.You grow all sorts of vegetables in the fields.
Some days of the year, you toil the soil all day planting carrots, tomatoes, lettuce, cabbage, beet, pepper and many others.
At night you are so tired that you sleep deeply and without any dreams.
The rains come and the fields become a deep luxuriant green with spots of red, yellow, orange, purple and patches of mint green.
One day while harvesting that season's carrots, you sit midday on a rock for a brief respite. Lines and lines of carrots extend in every direction.
The sun shines strongly above. You are thirsty and tired. Suddenly you see some leaves move slightly. As in a dream (perhaps you did indeed take a nap?) you see a neatly dressed carrot man approach you.
"Good day sir" says the carrot man. After a short pause as if expecting you to say something he continues "we see you working all day pulling our neighbors from the soil and we ask each other how long before we too will be taken from our homes?".
"I have never thought of it that way. I don't even know how many of you there are?" you mumble a bit embarrassed.
"There is a very simple way to estimate that sir. Imagine that there is one carrot being living at each integer set of coordinates (x,y) of this field.. Then you certainly can figure out how many carrots lie in the line between any two carrots at coordinates (x1,y1) and (x2,y2)? If you then extend your reasoning to find how many carrots are in a rectangle that has its diagonal given by the same line segment you can find out how many of us there are."
Having completed this discourse the carrot man turned and slowly walked to the neighboring row of carrots, past it and soon he had disappeared among the greenery.
After this conversation you hesitate going back to your carrot pulling task. You try to solve the problem posed by the carrot man instead. How many carrots there are in the line segment between two carrots? And how many carrots lie in a rectangle whose diagonal is given by the same line segment?
How many carrots on a line?
Cross Product
Given two carrots at (x1,y1) and (x2,y2) a simple strategy is the following:Consider all carrots that lie inside (but not on the border) of a rectangle where the lower left corner is at coordinates min(x1,x2), min(y1,y2) and the top right corner is at coordinates max(x1,x2),max(y1,y2).
We can check for each of these carrots whether they lie or not in the segment connecting (x1,y1) to (x2,y2). How?
Form the vector that joins the two ends of the segment. Its components will be (max(x1,x2)-min(x1,x2), max(y1,y2)-min(y1,y2)).
Then form the vector connecting the lower left corner of the rectangle at (min(x1,x2),min(y1,y2)) to the point inside the rectangle at integer coordinates (i,j).
This vector has coordinates (i-min(x1,x2)),j-min(y1,y2)).
The point lies on the segment when the angle between these 2 vectors is zero.
The cross product of these two vectors is the product of their magnitudes times the sin of the angle between them. Therefore the cross product will vanish if these two vectors are collinear, i.e. if the point lies on the segment.
The cross product is a vector parallel to the z axis (the axis perpendicular to the field where the carrots lay) with value
(i-min(x1,x2))*(max(y1,y2)-min(y1,y2)) - (j-min(y1,y2))*(max(x1,x2)-min(x1,x2))
All points inside the rectangle for which this difference is zero, are on the line segment.
Greatest Common Divisor (GCD)
Since we are dealing with integers, there is another way we can find the number of points using number theory.Without loss of generality we can always put the lower left corner of the rectangle at the origin of the coordinates (0,0) and the top right corner at the point (x2-x1,y2-y1) (assuming x2>x1 and y2>y1). The rectangle has sides of length (x2-x1) and (y2-y1).
All integer points on this segment must obey the line equation y=(y2-y1)/(x2-x1)x. Or y/x=(y2-y1)/(x2-x1).
Lets suppose that the GCD of (y2-y1) and (x2-x1) is ...GCD. We can write
y = GCD*p/(GCD*q)x
where p and q are relatively prime (coprime), i.e. they have no common divisors.
It is clear then that the following integer points are on the segment: (q,p), (2q,2p), (3q,3p),..., ((GCD-1)x, (GCD-1)y). Therefore there are GCD-1 integer points/carrots in the segment (excluding the endpoints).
For an example consider (x2-x1)=10 and (y2-y1)=15. Then y/x=3*5/(2*5). Pairs (2,3), (4,6), (6,9), (8,12) are all in the segment. The GCD is 5 and there are 4 points on the segment.
This also shows that if (x2-x1) and (y2-y1) are coprimes (i.e. they dont have any common divisors), there can not be any integer point lying on the segment (other than the endpoints).
Put another way dividing the rectangle of size (x2-x1,y2-y1) into the greatest number of identical rectangles is equivalent to finding the greatest common divisor of (x2-x1) and (y2-y1).
How many carrots in a rectangle?
Lets now look at the second question:How many carrots are inside the rectangle whose diagonal is the segment from (x1,y1) to (x2,y2)?
The easiest way to count those is to count them as we loop through every point of integer coordinates on or inside the rectangle.
But since the problem is so easy we can try to be clever and come up with a formula for this number.
To find out how many carrots are right on the rectangle border we could use the cross product or gcd methods above applied to each of the four sides of the rectangle. Actually the top and bottom sides will have the same number of carrots as will the left and right sides so we can just use two sides and multiply by two.
But it is easier to do things manually:
The bottom side will have (x2-x1)+1 points (because of the origin). Adding the top side this gives
2[x2-x1+1]. The left and right side contribute 2[y2-y1+1]. But 4 of the points are counted twice, so
the total number of carrots on the boundaries of the rectangle is
2[x2-x1+1+y2-y1+1-2]=2(x2-x1+y2-y1)
How many carrots will be inside the rectangle? Divide the rectangle by vertical lines parallel to its left and right sides and starting at integer values of x. There will be (x2-x1)-1 of those lines (excluding the left and right sides). For each of those lines there will (y2-y1)-1 points with integer y coordinates. So there will be a total of [x2-x1-1][y2-y1-1] interior carrots.
The total number of carrots in the rectangle (interior and boundary) is then
(x2-x1)(y2-y1)+ (x2-x1+y2-y1)+1
