# Paint the Rectangle with least number of Circular Stamp Touches

What is the minimum number of touches for painting at least a $100*100$ rectangle if you have one circular stamp tool that paints a circular area of $1$ unit radius in every touch?

This question is very similar to Paint the rectangle with least movement. But this time there is no brush tool for painting.

## 2 Answers

If you array circles with radius = 1 on a triangular as shown below, you can cover a rectangular area with

 height = (3n-1)/2, where n is the number of rows of circles, and

width = sqrt(3)(2m-1)/2, if each row is of length m, or
width = sqrt(3)(m-1), if alternate rows are of length m, and m-1


So you can cover a 100x100 square with 67 rows, of alternating length 59,58,59...(actual rectangular area covered is 100 high by ~100.459 wide).

Total number of circles used is 34x59 + 33*58 = 3920 • that totally sounds reasonable!! – Martin Frank Oct 9 '14 at 4:02
• If you start with a 58-row, the total number of circles used would be 34x58 + 33x59 = 3919. – Florian F Oct 9 '14 at 15:43

you might need w/2 x h/2 filled circles (even filled circles) on the first run and then need (w-1)/2 x (h-1)/2 filled circles (odd filled circles) to fill the gaps between... you can 'cut' pathes when you draw a even line and then switch to an odd line...

lenght of even line = 100; length of odd line = 99; path to switch from odd to even (and back) = Math.Squrt(2) (i'll say it's 1.4 for terms of easier use)...

so you have 100 x 100 + 99 x 99 + 99*1.4 = 10'000 + 9801 + 138.6 = 19939.6 (having rounding erros) BLACK  = even circles
RED    = odd circles
PURPLE = rectangle
GREEN  = path


i can't proof that this path would be shorter: • your second path (or solution) was shorter. but the question still stays unanswered, "what is the minimum number?" – Rafe Oct 8 '14 at 18:30
• I have [somehow] copied your answer up here – Rafe Oct 8 '14 at 18:35
• wow thank you @Rafe - i hope this will be a good start for discussion whereas i must confess the solution from penguino looks very nice as well... – Martin Frank Oct 9 '14 at 4:01
• There's no "paths" involved here, just numbers of circles. The second half of the first picture and the second picture can be removed, and as Rafe mentioned, there is no circle count. – TheRubberDuck Oct 9 '14 at 17:20