Problem N
Korncirkler
Lige inden høsten skal til at gå i gang, har nogen lavet korncirkler i markerne. Rued er bange for, at der er efterladt pæle i centrum af korncirklerne, som kan skade mejetærskeren. Han vil derfor gerne finde alle centre af korncirklerne.
Marken er et rektangel med bredde $b$ og højde $h$, dens sider flugter med kompasretningerne. Positionerne på marken er heltalskoordinater $(x,y)$ med $0\leq x < b$ og $0\leq y < h$. Markens nordvestlige hjørne er $(0,0)$.
En korncirkel har altid sit centrum i en heltalskoordinat $(c_ x,c_ y)$, og har radius $r>0$. Alle celler tættere på centrum end $r$ er lagt ned; specifikt er celler med koordinat $(x,y)$, hvor ${(x-c_ x)}^2+{(y-c_ y)}^2<r^2$, lagt ned.
Indlæsning
Den første linje er to heltal $b$ og $h$ adskilte af mellemrum. De næste $h$ linjer, hver med $b$ tegn, beskriver i hvilke koordinater kornet er blevet lagt ned som en del af en korncirkel. En celle er ».«, når kornet er uberørt, og »#«, når kornet er lagt ned.
Markens dimenioner er $b$ og $h$; der gælder $0 < b \leq 100$ og $0 < h \leq 100$.
To korncirkler overlapper aldrig og har mindst én celle af stående korn imellem sig.
Udskrift
Centrum $(c_ x,c_ y)$ for hver korncirkel, en linje per korncirkel.
Testgrupper
Der er to testgrupper. I testgruppe $1$ er der præcis én korncirkel.
Sample Input 1 | Sample Output 1 |
---|---|
15 15 ............... ............... ....###........ ..#######...... .#########..... .#########..... ###########.... ###########.... ###########.... .#########..... .#########..... ..#######...... ....###........ ............... ............... |
5 7 |
Sample Input 2 | Sample Output 2 |
---|---|
15 15 ............... ............... ............... ..###.......... .#####......... .#####......... .#####.###..... ..###.#####.... .....#######... .....#######... .....#######... ......#####.... .......###..... ............... ............... |
3 5 8 9 |