Po najnovšom rebrandingu KFC na KFC++ (o 1 lepšie ako predtým), sa rozhodli otvoriť novú prevádzku. A kde inde ju otvoriť ako uprostred preskúmaného vesmíru. Aby ste si vedeli predstaviť, tak všetok preskúmaný vesmír je vlastne taká dvojrozmerná mriežka v ktorej vrcholoch je buď nič - ‘.’ alebo hviezda - ‘#’. A ako si iste viete predstaviť vesmír má veľa toho prázdneho priestoru, ktorému nebude vadiť ak najbližšia prevádzka bude ďaleko. Preto sa najvyšší manažment rozhodol, že novú prevádzku postavia uprostred takzvanej “Hviezdokúpy”. “Hviezdokúpa” je obdĺžnikovou plochou, ktorá obsahuje všetky hviezdy preskúmaného vesmíru a zároveň neobsahuje žiadny zbitočný prázdny priestor (je najmenšou možnou hviezdokúpou). Lenže tak ako vždy, najvyšší manažment si niečo vymyslel, ale vyriešiť to zas musia brigádnici. Preto musíte vy, vyprážači/čky hranoliek a pokladníci/čky, nájsť tento stred “Hviezdokúpy” kde sa vybuduje nová prevádzka.
Naprogramujte program, ktorý v poli s $y$ riadkami a $x$ stĺpcami nájde bod, ktorý je stredom takého najmenšieho obdĺžnika, že všetky znaky # sa nachádzajú v jeho vnútri. (Tento obdĺžnik má steny rovnobežné s riadkami a stĺpcami)
V prvom riadku vstupu sú dve čísla $x$ a $y$ oddelené medzerou udávajúce rozmery našej hviezdokúpy. Nasleduje $y$ riadkov pričom každý riadok obsahuje $x$ znakov z ktorých každý je buď . alebo
V jednotlivých sadách platia nasledujúce obmedzenia:
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $1 \leq x, y \leq$ | $10$ | $100$ | $1000$ | $10^4$ |
Vypíš jeden riadok a v ňom dve čísla zaokrúhlené na presne jedno desatinné miesto oddelené medzerou, udávajúce súradnice $x$ a $y$ miesta novej prevádzky.
Input:
5 7
.....
.#.#.
..##.
.#...
.....
.###.
...#.
Output:
2.0 3.5
Vidíme, že najmenší obdĺžnik obsahujúci všetky hviezdy je obdĺžnik so vrcholmi (1,1), (3,1), (3,6) a (1, 6), ktorého stred je na súradnici (2,3.5)
Input:
2 2
..
..
Output:
0.5 0.5
Keď neexistujú žiadne hviezdy, tak vypíšeme stred vesmíru.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete