A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Egy befektető Manhattan szívében új luxus bevásárlóközpont építését tervezi. Jól tudja, hogy a legnagyobb látogatottság úgy érhető el, ha a helyszín minél közelebb esik a lehetséges vásárlókhoz. Ezért részletesen felmérte, hogy a város mely részéből hány vásárlóra lehet számítani, most pedig ‐ mint legjobb tanácsadóját ‐ minket kért meg, hogy javasoljunk számára olyan helyszínt, melynek eléréséhez átlagosan a lehető legkevesebbet kell utazniuk a vásárlóknak. Írjunk programot a feladat megoldására. A megoldás során a hagyományokhoz hűen Manhattan úthálózatát tekintsük egy (kétirányú utakból álló) szabályos rácsnak, melynek kereszteződései az egész koordinátájú pontokban vannak. Az egyszerűség kedvéért azonosítsuk a hozzájuk legközelebb eső kereszteződéssel mind a bevásárlóközpont, mind a vásárlók lakásainak helyét, a , koordinátájú kereszteződések távolsága pedig rács menti legkisebb távolságuk, azaz a következő legyen: | | A program a felmérés eredményét a standard bemenetről olvassa. Ennek első sora a felmért kereszteződések számát tartalmazza, az ezt követő darab sora pedig egy-egy kereszteződést ír le. Az -edik sorban egy-egy szóközzel elválasztva három egész szám, az -edik kereszteződés koordinátái, illetve az onnan várható vásárlók száma található. A fenti jelölésekkel tehát a bevásárlóközpont számára azt az optimális kereszteződést keressük, melytől a felmért kereszteződések ‐ az egy kereszteződésben lakók számával súlyozott ‐ átlagos távolsága minimális: | | A standard kimenet egyetlen sorába mindössze három, szóközzel elválasztott szám kerüljön: a bevásárlóközpont optimális helyszínének , koordinátái, illetve az ehhez tartozó átlagos távolság, 4 tizedes pontossággal. Több megoldás esetén bármelyik megadható.
Értékelés: a maximális 8 pont eléréséhez a programnak a legnagyobb teszteseteket is egy percen belül meg kell oldania, ugyanakkor már 5 pont szerezhető az feltételnek eleget tevő tesztesetek megoldásával is. További 2 pontot ér a dokumentáció. Beküldendő a feladat megoldását tartalmazó forrás és projektállományok (az .exe és más a fordító által generált kiegészítő állományok nélkül), valamint a megoldás menetét röviden bemutató dokumentáció (s59.txt, s59.pdf, ) egy tömörített mappában (s59.zip). |