NézetNyomtat

Régiók (Megoldás)
Címkék > Feladat

Régiók

Egy megyén belül a településeket régiókba szeretnék csoportosítani. Ismerjük az egyes települések koordinátáit. Két település távolságán a koordináta-különbségeik abszolút értékének összegét értjük, azaz $d((x,y),(a,b))=|x-a|+|y-b|$.

Két települést azonos régióba teszünk, ha egyikből a másikba el lehet jutni a régió településein keresztül úgy, hogy az egymást követő települések távolsága legfeljebb T kilométer.

Feladat

Írj programot, amely megadja, hogy a települések hány régiót alkotnak, és mely települések tartoznak egy régióba!

Bemenet

A REGIO.BE szöveges állomány első sorában a városok N száma $(2\le N\le 100)$ és a régióba kerülés határát jelentő T távolság $(1\le T\le 2000)$ van. A következő N sor mindegyikében egy-egy számpár van, az adott város x- és y-koordinátája (0 és 1000 közötti egész számok), egy szóközzel elválasztva.

Kimenet

A REGIO.KI szöveges állomány első sorába a legkisebb K számot kell írni, ahány régióba lehet besorolni a településeket. A következő K sorba az egyes régiókat kell írni, tetszőleges sorrendben. Egy sorba a régióba tartozó települések sorszámát kell írni, egy-egy szóközzel elválasztva, növekvő sorrendben.

Példa

regio.beregio.ki
6 50 100 100 100 220 100 120 300 100 120 240 310 90 3 1 3 5 2 4 6

Tesztadatok