NézetNyomtat

Csokoládés keksz (Megoldás)
Címkék > Feladat

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