ACM RTK - 1. skupina

Kolera

V devetnajstem stoletju se še ni kaj dosti vedelo o načinu prenašanja nalezljivih bolezni. Leta 1854 so imeli v Londonu velik izbruh črevesne bolezni kolere. Zdravnik John Snow je takrat s svojo analizo pokazal na vzročno zvezo med lokacijo londonskih vodnjakov in lokacijo domovanja obolelih. Izkazalo se je, da so žrtve pile vodo iz istega okuženega vodnjaka na ulici Broad Street. Zdravnik si je narisal zemljevid Londona, vanj vrisal lokacije vodnjakov in za vsak vodnjak z drugo barvo pobarval območje zemljevida, ki je temu vodnjaku najbližje. Ko je vrisal še točke domovanja obolelih, je postala vzročna zveza precej očitna, saj so prebivalci večinoma hodili po vodo k njim najbližjemu vodnjaku.

Nekoliko si poenostavimo zemljevid velemesta in denimo, da nas zanima le območje, ki ga razdelimo na kvadratno mrežo 50 × 50 celic. V nekaterih celicah te mreže se nahajajo vodnjaki. Vseh vodnjakov je deset, njihove koordinate preberemo z vhodne datoteke: v vsaki vrstici sta dve celi števili, x in y (obe sta z območja od 1 do 50).

Napiši program, ki bo prebral koordinate vodnjakov, potem pa za vsak vodnjak izpisal, kolikšno površino zemljevida pokriva, t.j. kolikšnemu številu celic v tej pravoko- tni mreži je ta vodnjak najbližji. Za merjenje razdalje med dvema celicama uporabimo Pitagorov izrek: kvadrat razdalje med (x₁, y₁) in (x₂, y₂) je (x₁ − x₂)² + (y₁ − y₂)². Če je od neke celice razdalja do več vodnjakov enaka, je vseeno, h kateremu vodnjaku štejemo tako celico. Tvoj program lahko bere s standardnega vhoda ali pa iz datoteke kolera.txt (kar ti je lažje).

Prikazan je seveda le eden od številnih možnih izpisov pri teh vhodnih podatkih (saj naloga pravi, da če je neka celica enako oddaljena od dveh ali več vodnjakov, je vseeno, h kateremu jo štejemo). Črne pike na sliki označujejo položaje vodnjakov, osenčeni liki pa kažejo dele mreže, ki so najbližje posameznemu vodnjaku.