Županijsko natjecanje 2014. godine za 1. i 2. razred Srednje Škole - 2. zadatak

Pojavom tableta i mobitela s ekranima osjetljivima na dodir, fizičke tipkovnice lagano odlaze u zaborav. Međutim, jedan problem s tipkovnicama na ekranima je veća mogućnost pogreške prilikom tipkanja, posebno kada je riječ o relativno malenim ekranima.

Za ovu priliku pretpostavimo da se tipkovnica sastoji od skupa pravokutnika u standardnom koordinatnom sustavu (koordinata X raste sa lijeva na desno, koordinata Y raste odozdo prema gore) kao na slici gore. Tipkovnica je definirana na sljedeći način:

• Svaki pravokutnik je širine 300 te visine 200.
• Između svaka dva pravokutnika u istom ‘redu’ se nalazi horizontalni razmak od točno 20.
• Između dva susjedna reda je vertikalni razmak od točno 20.
• Donji lijevi kut pravokutnika koji sadrži slovo ‘Q’ je na koordinatama (0, 440).
• Donji lijevi kut pravokutnika koji sadrži slovo ‘A’ je na koordinatama (150, 220).
• Donji lijevi kut pravokutnika koji sadrži slovo ‘Z’ je na koordinatama (470, 0).

Na temelju ovih pravila i rasporeda tipaka danog u slici gore, mogu se odrediti koordinate pravokutnika za svako slovo. Tako su, na primjer, donji-lijevi i gornji-desni kutovi pravokutnika koji sadrži slovo ‘J’ jednaki (2070, 220) i (2370, 420) redom. Središte pravokutnika definiramo kao polovište dužine između dva suprotna kuta pravokutnika. Tako je, na primjer, središte pravokutnika koji sadrži slovo ‘J’ točka (2220, 320). Primijetite da kutovi svih pravokutnika imaju parne X i Y koordinate, pa stoga središte svakog pravokutnika ima cjelobrojne koordinate.

Zadan je niz od N točaka u koordinatnom sustavu - to su koordinate gdje je korisnik redom dodirnuo ekran. Za svaki dodir kažemo da je korisnik stisnuo slovo ako se točka nalazi unutar ili na rubu odgovarajućeg pravokutnika.

Podzadatak A. Napiši program koji će za svaku od N točaka odrediti koje je slovo korisnik stisnuo te ispisati ili nađeno slovo ili znak ‘?’ ako točka ne odgovara niti jednom slovu.

Podzadatak B. Dodatno, zadan je rječnik koji se sastoji od M riječi, a svaka riječ od točno N velikih slova engleske abecede. Vaš program treba odrediti koja je riječ iz rječnika najbliža zadanom nizu točaka.

Udaljenost riječi i niza točaka se definira kao suma udaljenosti i-te točke do i-tog slova u riječi za sve i između 1 i N. Udaljenost slova do točke se definira kao kvadrat euklidske udaljenosti između točke i središta pravokutnika koji odgovara tom slovu. Drugim riječima, ukoliko je stisnuta točka (X1,Y1) , a središte pravokutnika nekog slova se nalazi na koordinatama (X2,Y2) , onda je udaljenost točke od tog slova jednaka (X1-X2)^2 + (Y1-Y2)^2. Ukoliko ima više najbližih riječi, potrebno je ispisati onu koja se ranije pojavljuje u rječniku

ULAZNI PODACI

U prvom redu nalaze se dva prirodna broja, N i M (N ≤ 10, M ≤ 100) međusobno odvojena razmakom - broj točaka i broj riječi u rječniku.

Nakon toga slijedi N redova od kojih svaki sadrži dva cijela broja X, Y (-5000 ≤ X, Y ≤ 5000) - koordinate odgovarajuće točke.

Nakon toga slijedi M redova, svaki sadrži jednu riječ od točno N velikih slova engleske abecede. Sve riječi će biti različite i bit će poredane abecedno.

IZLAZNI PODACI

U prvi red potrebno je ispisati niz od N znakova (bez razmaka između pojedinih znakova) gdje je svaki znak ili veliko slovo engleske abecede ili znak ‘?’ - rješenje podzadatka A.

U drugi red izlaza potrebno je ispisati jednu od riječi iz rječnika - rješenje podzadatka B.

PRIMJERI TEST PODATAKA

ulaz

6 1
2070 220
2069 220
2070 219
2370 420
2371 420
2370 421
SLAVKO

izlaz

J??J??
SLAVKO

ulaz

4 5
2451 364
2262 433
2202 154
2616 517
JOZO
KINO
KRIO
MIRO
RIKO

izlaz

K?NO
KINO

ulaz

5 6
912 334
306 358
462 349
-102 340
770 200
ASADQ
DAASA
DANAS
QAZAD
SADAS
SDEFE

izlaz

DA??Z
SADAS