Csokoládés keksz
Kekszet sütünk csokoládé darabkákkal (Cookie with chocolate chips). A tésztába keverjük a csoki darabokat, majd téglalap alakúra nyújtjuk a tésztát. Ezután egy kör alakú szaggatóval vágjuk ki a sütésre váró sütiket. Az első darabot úgy szeretnénk kivágni a tésztából, hogy a lehető legtöbb csoki kerüljön bele. A csokik látszanak a tészta felületén.
Hogyan kell vágnunk a maximális mennyiségű csokihoz? (A kör széle kilóghat a tésztáról,
tehát lehet, hogy egy széle egyenes a sütinek.)
Feladat
Egy téglalap alakú tartományban (tészta) adott néhány pont (pontszerű csokik, elég diétás). Adott továbbá egy rögzített sugarú kör.
Legfeljebb hány pontot tudunk lefedni az adott sugarú körrel?
(A téglalap 500-szor 500-as, bal alsó sarka az origó.)
Bemenet
Első sor: A csokik száma=n, ez legfeljebb 500; a kör sugara=r.
Ezután n sorban a csokik x, y koordinátája. A koordináták egészek,
0 és 500 között. A kör sugara egész, 2 és 10 között.
Kimenet
A csokik maximális száma az elsőként kivágott kekszben.
Példa
CSOKI.BE CSOKI.KI
8 2 4
1 1
5 1
5 2
8 1
3 2
3 3
7 5
7 3
Tesztadatok
