Kezdőlap


Feladat:	S.49	Korcsoport: -	Nehézségi fok: -
Füzet:	2009/december, 555. oldal		PDF \| MathML
Témakör(ök):	Nehezebb feladat

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.

Bergengócia környezettudatos ország. Azt tervezik, hogy a teherszállítást hidrogénnel hajtott járművekkel oldják meg. A hidrogént cseppfolyósítva lehet ‐ a benzinhez hasonlóan ‐ nagybiztonságú tárolótartályokból a teherautókba tölteni. Sajnos még kevés töltőállomás van. Hidrogén üzemanyagú teherszállítást ott lehet alkalmazni, ahol a hidrogénkutak legfeljebb $K$ kilométer távolságban vannak egymástól.
A bergengócok pontosan nyilvántartják a hidrogénkutak koordinátáit. Két kút távolságán a koordináta-különbségek abszolút értékének összegét értik:

\begin{matrix} T = | x_{1} - x_{2} | + | y_{1} - y_{2} | . \end{matrix}

Segítsük a bergengóc teherszállítás tervezőit azzal, hogy a hidrogénkutakat csoportosítsuk. Két kutat egy csoportba teszünk, ha az egyiktől a másikig el lehet jutni a csoport kútjait érintve úgy, hogy az egymást követő kutak távolsága legfeljebb

K

kilométer.
Készítsünk programot, amely megadja, hogy a hidrogénkutak hány csoportot alkotnak és melyek tartoznak egy csoportba.
A program a parancssor első argumentumaként megadott bemeneti állomány első sorából beolvassa a hidrogénkutak

N

(

3 \leq N \leq 200

) számát,

K

(

100 \leq K \leq 500

) távolság értékét, majd a következő

N

sorból a kutak

x

;

y

(

0 \leq x; y \leq 1000)

koordinátáit.
A parancssor második argumentumaként megadott kimeneti állomány első sorába írjuk a csoportok

D B

számát, majd a következő

D B

sorba az egy csoportba tartozó hidrogénkutak sorszámát szóközzel elválasztva.

Beküldendő egy tömörített állományban (s49.zip) 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 bemutató dokumentáció.