Kezdőlap


Feladat:	S.59	Korcsoport: -	Nehézségi fok: -
Füzet:	2011/január, 37 - 38. oldal		PDF \| MathML

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 $p_{i} = (x_{i}, y_{i})$ , $p_{j} = (x_{j}, y_{j})$ koordinátájú kereszteződések távolsága pedig rács menti legkisebb távolságuk, azaz a következő legyen:

\begin{matrix} d (p_{i}, p_{j}) = | x_{j} - x_{i} | + | y_{j} - y_{i} | . \end{matrix}

A program a felmérés eredményét a standard bemenetről olvassa. Ennek első sora a felmért kereszteződések

1 \leq N \leq 1 000 000

számát tartalmazza, az ezt követő

N

darab sora pedig egy-egy kereszteződést ír le. Az

i + 1

-edik sorban egy-egy szóközzel elválasztva három egész szám, az

i

-edik kereszteződés

0 \leq x_{i}, y_{i} \leq 1 000 000

koordinátái, illetve az onnan várható vásárlók

1 \leq w_{i} \leq 1000

száma található.
A fenti jelölésekkel tehát a bevásárlóközpont számára azt az optimális

p_{0}

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:

\begin{matrix} \bar{D} = \frac{\sum_{i = 1}^{N} d (p_{0}, p_{i}) \cdot w_{i}}{\sum_{i = 1}^{N} w_{i}}, ahol p_{i} = (x_{i}, y_{i}) . \end{matrix}

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

p_{0}

helyszínének

x_{0}

y_{0}

koordinátái, illetve az ehhez tartozó

\bar{D}

á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

N \leq 1000

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