Page 16 - MATINF Nr. 11-12

16 D.A. Popescu, C. B˘alc˘au, D. Constantin

octogon.in octogon.out
2 17500
10
0 50
80 40
100 0
100 150
150 50
50 150
150 100
40 80
0 100
50 0

Timp maxim de execut , ie: 5 secunde/test.
a
Memorie total˘ disponibil˘a: 2 MB.
Solut , ie

Cerint , a 1 ( 20 puncte)

Se parcurg perechile de noduri s , i se num˘ar˘ cele care definesc un segment paralel cu una din
a
axe.
Cerint , a 2 ( 80 puncte)

Se foloses , te metoda backtracking. Se obt , in submult , imi de 8 puncte cu verificare part , ial˘a
a
a
legat˘ de pozit , ia punctelor ˆın acelas , i semiplan fat , ˘ de dreapta ce cont , ine punctul curent s , i cel
anterior generat.

Clasele a XI-a s , i a XII-a

Problema 1 – componente
Cerint , e

Se dau n puncte ˆın plan, numerotate cu 1, 2, . . . , n, prin coordonatele lor. Unele dintre
puncte sunt unite prin m segmente astfel ˆıncˆat s˘a se formeze una sau mai multe componente
conexe (nodurile grafului neorientat sunt puncte, iar muchiile sunt segmente). Se cere:
1. num˘arul de componente conexe cu cel put , in dou˘a noduri;

a
2. suma minim˘ a lungimilor segmentelor ce pot completa desenul astfel ˆıncˆat s˘ se obt , in˘ o
a
a
a
singur˘ component˘a conex˘a cu cel put , in dou˘a noduri.
Date de intrare
Pe prima linie a fis , ierului de intrare componente.in se afl˘a C – cu valorile 1 sau 2, pe a
doua linie n s , i m separate printr-un spat , iu, pe urm˘atoarele n linii coordonatele punctelor, iar ˆın
continuare pe urm˘atoarele m linii perechi de numere ce corespund capetelor segmentelor date.

Date de ies , ire
a
a
Dac˘ C este 1, fis , ierul de ies , ire componente.out va cont , ine num˘arul de la cerint , a 1. Dac˘ C
este 2, fis , ierul de ies , ire componente.out va cont , ine partea ˆıntreag˘ a num˘arului de la cerint , a 2.
a