Page 123 - MATINF Nr. 3

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 123

Restrict , ii s , i preciz˘ari

• 2 ≤ n ≤ 10
• 2 ≤ m ≤ 15
• Costurile muchiilor sunt numere cu maxim dou˘a cifre
• Pentru toate testele exist˘a solut , ie!

Exemplu
aps.in aps.out Explicatie
4 5 80 1 2 Graful cont , ine un arbore part , ial format
1 2 10 1 4 din muchiile [1, 2], [1, 4] s , i [4, 3],
4 2 30 4 3 avˆand costul egal cu 80.
2 3 80
1 4 20
4 3 50

Timp maxim de execut , ie: 1 sec./test. Memorie total˘a disponibil˘a 2 MB.
***
I 45 (campanie). Se dau N puncte ˆın plan prin coordonatele lor. Determinat , i aria poligonului
cu vˆarfurile ˆın unele din punctele date s , i care cont , ine pe laturi sau ˆın interior toate cele N
puncte.
Cerint , ˘a

Cunoscˆand N s , i perechile de numere ce reprezint˘a coordonatele a N puncte, determinat , i
aria poligonului cu vˆarfurile ˆın unele din punctele date s , i care cont , ine pe laturi sau ˆın interior
toate cele N puncte.

Date de intrare
ˆ
In fis , ierul aria.in se afl˘a pe prima linie N, iar pe urm˘atoarele N linii abscisa s , i ordonata,
separate prin cˆate un spat , iu, pentru punctele date.

Date de ies , ire
Fis , ierul aria.out cont , ine pe prima linie num˘arul reprezentˆand rezultatul cerint , ei.

Restrict , ii s , i preciz˘ari
• 3 ≤ N ≤ 1000
• Coordonatele punctelor sunt numere ˆıntregi din intervalul [−10000, 10000]
• Pentru toate testele exist˘a cel put , in trei puncte necoliniare

Exemplu
aria.in aria.out Explicat , ie
7 50 Poligonul c˘autat are vˆarfurile ˆın punctele (0, 0),
0 10 (5, 0), (5, 10) s , i (0, 10). Aria sa este egal˘a cu 50.
5 0
5 5
0 0
5 10
2 2
2 5

Timp maxim de execut , ie: 0.1 sec./test. Memorie total˘a disponibil˘a 2 MB.
***