|
|
back to boardWell, this is for those who didnt get the method.
Consider N: no of rows of blocks M: no of columns of the blocks (N+1 and M+1 are the input).
Crosspoint here refers to a point where a horizontal and a vertical line meet.
For each line that the plane intersects, a new block is introduced. Consider the south western most point also as one such point. No of horizontal lines intersected=N. No of vertical lines intersected=M. But the southwestern most point has been counted twice and it introduces the same first block.
If gcd(M,N)==1, there is no intermediate point where the line passes over a crosspoint. Hence no. of blocks = M+N-1.
If gcd(M,N)!=1, the whole grid can be split horizontally at
the points where the line passes over a crosspoint and each of them can be considered separately with that cross point as the south westernmost point of the subproblem. There are gcd(M,N) such points. Say a=gcd(M,N). Then in each subproblem the line flies over M/a+N/a-1 blocks. Totally the line flies over a*(M/a+N/a-1) blocks. ie. M+N-a blocks.
Edited by author 29.11.2007 02:42
Edited by author 26.09.2015 00:39 Or you can do it simply by tracing error:
int filled_pixels = 0;
long long error = 0;
for (int x = 1; x <= dx; x++)
{
filled_pixels++;
error += dy;
if (error >= dx)
{
error -= dx;
if (error != 0)
filled_pixels++;
}
}
The code is incomplete, but the idea should be clear. We need to maintain error. When we exceed this threshold, that means we have crossed horizontal line. M+N-a works in any case, even if gcd(M,N)=1, right? |
|
|
