Minimum Sprinklers Problem

In this problem, you are given the dimensions of a rectangular garden and the radius of a sprinkler. Your task is to determine the minimum number of sprinklers required to cover the entire garden and to output the coordinates at which to place each sprinkler.

The sprinklers are assumed to cover a circular area with a given radius r. To ensure full coverage of the garden, the sprinklers are placed on a grid. Specifically, the centers are placed starting at coordinate (r, r) and with a gap of 2r in both x and y directions. However, if the computed coordinate exceeds the garden boundary, it is adjusted to lie on the edge of the garden.

The garden is represented by its width W and height H. For example, for a garden of width 8 and height 8 with sprinklers of radius 3, the optimal placement would be at positions (3, 3), (3, 8), (8, 3), and (8, 8).

Note: All formulas are in \( \LaTeX \) format. The gap between sprinkler centers is given by \(2r\), and each sprinkler covers a circular area of radius \(r\). The candidate should implement the solution to compute the minimal grid placement and output the results accordingly.

inputFormat

The input consists of a single line with three space-separated integers:

• W: the width of the garden.
• H: the height of the garden.
• r: the radius of each sprinkler.

outputFormat

The output should begin with an integer representing the minimum number of sprinklers required. This is followed by that many lines, each containing two space-separated integers representing the x and y coordinates of a sprinkler. If a computed coordinate exceeds the garden boundary, it should be replaced by the corresponding boundary value.

## sample

8 8 3

4
3 3
3 8
8 3
8 8

</p>