Page 169 - MATINF Nr. 1

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 169

Exemple

veverita.in veverita.out Explicat , ie
1 1 p = 1
5 8 Veverit , a poate s˘a sar˘a ˆıntre pomii:
5 12 1 s , i 3, 3 s , i 5, 2 s , i 4.
100 14 Trebuie s˘a ris , te s˘a mearg˘a pe jos
2 8 o singur˘a dat˘a ˆıntre doi pomi.
100 8
10 8

veverita.in veverita.out Explicat , ie

2 90 p = 2
5 8 Veverit , a poate s˘a sar˘a ˆıntre pomii:
5 12 1 s , i 3, 3 s , i 5, 2 s , i 4.
100 14 Trebuie s˘a mearg˘a pe jos ˆıntre po-
2 8 mii 4 s , i 5 pe o distant , ˘a egal˘a cu
100 8 90.
10 8

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 4 MB, din care 2 MB pentru stiv˘a.

Doru Anastasiu Popescu, Pites , ti, Gabriel Nicolae, Bucures , ti (Info-Oltenia, 2016)

I 15 (case). Cu mult timp ˆın urm˘a, mai multe case s-au construit f˘ar˘a un plan urbanistic,
ˆ
formˆand o comun˘a. In zilele noastre, primarul comunei vrea s˘a ˆımpart˘a comuna ˆın sate pentru
a gestiona mai us , or problemele comunit˘at , ii. Pentru a simplifica lucrurile, primarul dores , te
ca satele s˘a aib˘a suprafat , a p˘atratic˘a cu laturile paralele cu axele h˘art , ii. Primarul cunoas , te
coordonatele caselor, casele fiind numerotate cu 1, 2, . . . , n, coordonatele colt , urilor din stˆanga-jos
s , i laturile suprafet , elor celor k sate. Satele sunt numerotate cu 1, 2, . . . , k. Suprafet , ele satelor
sunt disjuncte. Din p˘acate se poate ˆıntˆampla ca unele case s˘a fie ˆın afara satelor.

Primarul dores , te s˘a acceseze fonduri europene pentru un sistem de canalizare pe care s˘a-l

dezvolte ulterior. Pentru acest lucru ˆıntocmes , te un plan fiec˘arui sat, ˆın care traseaz˘a segmente
ˆıntre anumite case astfel ˆıncˆat s˘a se formeze un poligon convex; pe acolo va trece sistemul de
canalizare, astfel ˆıncˆat toate casele satului care nu sunt legate prin aceste segmente s˘a fie ˆın
interiorul poligonului.

Cerint , ˘a
Cunoscˆand numerele n, k, coordonatele caselor s , i datele suprafet , elor satelor (coordonatele
colt , ului stˆanga-jos s , i lungimea suprafet , ei), determinat , i:

1. num˘arul de case care nu fac parte din niciun sat;

2. num˘arul de case ce vor face parte din sistemul de canalizare al fiec˘arui sat i, i = 1, 2, . . . , k.