Feladat: I/S.28 Korcsoport: - Nehézségi fok: nehéz
Füzet: 2018/szeptember, 359 - 360. oldal  PDF  |  MathML 
Témakör(ök): Nehezebb feladat, Számítástudomány

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 hatalmas telekre sportkomplexumot terveznek. A telekre gondolatban egy koordináta-rendszert helyeznek. A kialakítandó N darab sportpálya mind téglalap alakú, oldalaik a koordináta-rendszer tengelyeivel párhuzamosak. Ismerjük minden pálya két szemközti csúcsának koordinátáit. A pályáknak nincs közös területe, de oldalaik érintkezhetnek egymással. A tervek szerint két pálya között pontosan akkor készül majd átjáró, ha legalább D hosszú szakaszon érintkeznek egymással. Egy pálya egy oldalát a vele érintkező más pályák több szakaszra osztják (ha nem, akkor a teljes oldalt egy szakasznak tekintjük). Vegyük azokat a szakaszokat, amik a külső térre néznek, vagyis nem részei más pálya oldalának. Egy-egy ilyen, legalább D hosszú szakaszra bejáratot terveznek. Adjuk meg, hogy a sportkomplexum tervében összesen hány bejárat és hány átjáró van.

 
 

Bemenet: az első sor a pályák N számát és a D hosszúságot tartalmazza. A következő N sor mindegyike négy egész számot tartalmaz: egy-egy pálya két szemközti csúcsának koordinátáit.
Kimenet: egy sorba írjuk ki az átjárók, aztán a bejáratok számát.
 
Bemenet (a  /  jel sortörést helyettesít)Kimenet   9 29 22   2 8 10 4 / 7 13 9 8 / 9 9 12 8 / 10 6 12 4 / 12 10 14 29 14 15 10 / 2 11 7 8 / 3 4 5 2 / 7 4 9 3
 

Korlátok: 1N105, -109koordináták109, 1D109, egész számok.
Értékelés: a pontok 20%-a kapható, ha D=1; további 20% kapható, ha a pályák 1×1-es négyzetek; további 20% kapható, ha N1000; további 40% kapható az eredeti korlátokra.
Időlimit: 0,3 mp, memórialimit: 100 MiB.