A Jack Straws egy társasjáték, amelyben néhány műanyag vagy fa pálcikát szórnak egy asztalra, és a játékosok megpróbálják egyesével felemelni azokat anélkül, hogy a többi pálcika megmozdulna. Most csak azok a pálcikák zavarják egymást, amelyek összeköthetők csatlakozó pálcikák sorozatával. Adott pálcikák végpontjainak egy listája (mintha a pálcikák egy elég nagy asztalra lennének leszórva), és el kell döntenünk, hogy néhány adott pálcika csatlakozik-e egymáshoz. Megjegyezzük, hogy érintkező vagy metsző pálcikák csatlakoznak, de két pálcika indirekt módon is csatlakozhat, más pálcikákon keresztül.
Bemenet:
Az input első sora egy n (1<n<13) egész számot tartalmaz; n az asztalon lévő pálcikák száma. A következő n sor mindegyike négy pozitív egész számot tartalmaz; x1, y1, x2, y2. Ezek egy-egy pálcika (x1, y1) és (x2, y2) végpontjainak koordinátái. Minden koordináta kisebb, mint 100. Megemlítjük, hogy a pálcikák különböző hosszúságúak is lehetnek Az inputban elsőként szereplő pálcika sorszáma 1, a másodiké 2, és így tovább. Az input fennmaradó sorai (kivéve az utolsót) két-két pozitív egész számot tartalmaz; a és b mindegyike 1 és n között lehet, beleértve a határokat is. Határozzuk meg, hogy az a és b sorszámú pálcikák csatlakoznak-e egymáshoz! Ha a=b=0, akkor az input nem tartalmaz több sort. Feltehetjük, hogy nincs 0 hosszúságú pálcika, valamint az input adatok a leírt határokon belül vannak!
Kimenet:
Az outputnak minden (a,b) párra egy sort kell tartalmaznia, kivéve az utolsó párt, amikor is a=b=0! A sor tartalma ’Csatlakoznak’, ha az a és b pálcikák csatlakoznak egymáshoz, és ’Nem csatlakoznak’, ha az a és b pálcikák nem köthetők össze más pálcikákon keresztül. Minden pálcikát önmagához csatlakozónak tekintünk.
Példa:
|
INPUT.TXT |
OUTPUT |
|
7
|
Csatlakoznak
|
(ACM regionális verseny 1994)