Today Zoro was attending the class of computer graphics. He was very much interested in today's topic. The topic was to generate a circle with the given center and radius.
As you all might be aware that drawing any figure on a computer screen is to be dealt with handling PIXELS on a computer screen. A pixel is nothing but a coordinate on a computer screen. To draw a figure you need to fill that particular pixel. The main issue with this is that a pixel or a coordinate on a computer screen is mostly an integer, So if the resolution is less then a shape might appear distorted on the screen.
While constructing any figure you need to keep in mind the pixel you need to select in order to make it.
Zoro came to know about the Circle Constructing Algorithm with center (0,0). The algorithms says that:
Start with the point (0,R) (R is the radius of the circle). To choose the second point we have two options, (1,R) or (1,R-1). So to select the point the algorithm instructs to find the mid point of the points and check the proximity of the previous point with the mid point.
We have to select the point which is at a closer proximity. Now to Simply we sum up the calculations it is decided with the help of ,
the decision parameter.
1. If < 0:
we select the next point as (X+1,Y), .
2. If >= 0:
the next point will be (X+1,Y-1),
Where (X ,Y) is the point for particular k value and initially is considered to be 1-R.
Now an interesting observation in the following mapping of points is that points will be symmetrical of course in each quadrant.
But another specific detail is that points are symmetric across the line X=Y in a particular way.
Now Zoro is a bit dumb with coordinates and programming. So he wants to know all the points not crossing the line X=Y (not past the line X=Y) starting from (0,R). You have to find the points after (0,R) .
Can you help Zoro pass Computer Graphics ?
Constraints
1<=R<=1000000
Input
A single integer denoting radius of the circle.
Output
All coordinates desired in the problem.
The output is generated while following the algorithm and the coordinates are stopped at X=Y.