Zadanie

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.

Úloha

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)

Formát vstupu

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\)

Formát výstupu

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.

Príklad

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.

Ako prvé si môžeme všimnúť, že keď chceme nájsť stred najmenšieho obdĺžnika, ktorý obsahuje všetky znaky #, tak musíme nájsť okraje tohto obdĺžnika. Stred získame tak, že nájdeme stred medzi pravým a ľavým okrajom a stred medzi horným a dolným okrajom. Ako však vieme tieto okraje nájsť?

Ukážeme si to pre pravý okraj. Aby sme dostali pravý okraj, musíme nájsť taký stĺpec, pre ktorý platí, že všetky znaky # sú buď v ňom alebo naľavo od neho. Takže s pozíciou \(x\) menšou alebo rovnou tomuto stĺpcu. Keďže chceme najmenší obdĺžnik, tak chceme najlavejší takýto stĺpec. A ten bude obsahovať #. Ak by neobsahoval #, tak by sme mohli stĺpec posunúť viac doľava a stále by sme mali platný obdĺžnik. Takže nájdeme najľavejší stĺpec, ktorý obsahuje # a to bude pravý okraj.

Takto sa vieme pozrieť na všetky okraje. Dojdeme k tomu, že hľadáme pozíciu najvyššieho, najnižšieho, najviac vľavo a najviac vpravo položeného #, a to budú okraje našeho obdĺžnika.

Ako vieme teda nájsť # ktoré je najviac vľavo a ktoré je najviac v pravo? Môžeme si prejsť celé pole a v každom riadku nájsť prvý a posledný výskyt # a následne tieto hodnoty porovnať s doterajšími krajnými #. Ak sú viac na kraji, ako doterajšie maximum tak si ho prepíšeme. Takto získame súradnice \(x_l\) a \(x_p\) a výsledná hodnota \(x\) pre stred obdĺžnika bude ich priemerom.

Horné a dolné # zistíme tak, že keď budeme prechádzať každý riadok a narazíme na prvé #, tak tento riadok bude horný okraj. Uložíme si ho do \(y_h\). Spodným okrajom bude posledný riadok, v ktorom sme uvideli #. Ten si označme ako \(y_d\). \(y\)-ová súradnica stredu bude teda priemer \(y_h\) a \(y_d\).

Pri riešení si treba dať pozor, či na vstupe bolo aspoň raz #. Ak nie, musíme vypísať stred odĺžnika tak, aby bol stredom celej galaxie. Takže \(0\)-tého a \(x-1\)-ého stĺpca a \(0\)-tého a \(y-1\)-ého riadka.

Keďže na vstupe dostávame postupne riadky, vieme ich vyhodnocovať tiež postupne. Tým vieme znížiť pamäťovú zložitosť nášho riešenia na \(O(x)\). Kebyže veľmi chceme, vstup vieme načítavať znak po znaku, čím dosiahneme konštantnú pamäťovú zložitosť. To ale naprogramovať v pythone nie je až také jednoduché a presahuej to rámec tohoto vzoráku. Ako to spraviť v C++ si môžete pozrieť vo vzorovom riešení (ktoré pribudne po doprogramovávaní).

Časová zložitosť bude \(O(x \cdot y)\), keďže musíme prejsť celý vstup. Pre každý znak spravíme konštantne veľa operácií.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.