Page 99 - MATINF Nr. 4

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 99

I 59 (patrate). Se dau N puncte distincte ˆın plan prin coordonatele lor s , i culoare. Determinat , i
toate p˘atratele cu vˆarfurile ˆın mult , imea de puncte date, care au aceeas , i culoare.

Cerint , ˘a
Pentru N puncte ˆın plan date prin coordonatele lor s , i culoare, determinat , i num˘arul de
p˘atrate cu vˆarfurile ˆın mult , imea de puncte date, colorate la fel.

Date de intrare

Pe prima linie a fis , ierului patrate.in se afl˘a N. Pe urm˘atoarele N linii se afl˘a triplete de
numere reprezentˆand coordonatele (abscisa ordonata) s , i culoarea punctelor, separate prin cˆate
un spat , iu.

Date de ie¸sire

Pe prima linie a fi¸sierului patrate.out se va scrie num˘arul din cerint , ˘a.

Restrict , ii s , i preciz˘ari

• 2 ≤ N ≤ 10000
• Coordonatele punctelor sunt numere naturale cu maxim 5 cifre
• Culorile sunt date prin numere din mult , imea 0,1,2, ..., 15
Exemplu

patrate.in patrate.out Explicat , ie
5 1 Exist˘a un singur p˘atrat cu
0 0 9 vˆarfurile ˆın mult , imea de puncte date
5 0 9 colorate la fel, format din primele patru puncte.
5 5 9
0 5 9
10 0 1

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

Memorie total˘a disponibil˘a 2 MB.

Costel B˘alc˘au, Pites , ti
I 60 (romb). Se dau N puncte ˆın plan prin coordonatele lor. Determinat , i aria maxim˘a a unui
romb cu vˆarfurile ˆın mult , imea de puncte dat˘a.
Cerint , ˘a

Cunoscˆand N s , i perechile de numere ce reprezint˘a coordonatele a N puncte, determinat , i
aria maxim˘a a unui romb cu vˆarfurile ˆın mult , imea dat˘a.

Date de intrare
ˆ
In fis , ierul romb.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 romb.out va cont , ine pe prima linie num˘arul reprezentˆand rezultatul cerint , ei, trun-
chiat la dou˘a zecimale.