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.
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.be | regio.ki |
| 6 50 100 100 100 220 100 120 300 100 120 240 310 90 | 3 1 3 5 2 4 6 |