Rezolvare PBinfo #962

Se desenează n cercuri distincte în planul P, numerotate cu numerele de la 1 la n. Pentru fiecare cerc k (k∈{1,2,...,n}) se cunosc: raza cercului, rk, şi coordonatele (xk,yk) ale centrului cercului, coordonate referitoare la reperul cartezian xOy cu originea în punctul O a planului P. Din punctul O, se desenează m drepte distincte, astfel încât pentru fiecare dreaptă, dintre cele m desenate, să existe cel puţin un cerc, dintre cele n, al cărui centru să fie situat pe aceasta şi pentru fiecare cerc desenat, să existe o singură dreaptă, dintre cele m desenate, care să treacă prin centrul lui.

Cerinţă

Să se scrie un program care să se determine:
a) numărul m de drepte distincte;
b) cel mai mare număr q de cercuri, dintre cele n, exterioare două câte două, ale căror centre sunt situate pe o aceeaşi dreaptă care trece prin punctul O, dintre cele m desenate;
c) numărul p al dreptelor distincte, dintre cele m desenate, pe care sunt situate centrele a câte q cercuri, dintre cele n, exterioare două câte două.

Date de intrare

Fișierul de intrare cerc4.in conține pe prima linie numărul n de cercuri, iar pe următoarele n linii câte trei numere x y r, reprezentând coordonatele centrului și raza fiecărui cerc.

Date de ieșire

Fișierul de ieșire cerc4.out va conține o singură linie pe care se vor scrie cele trei numere naturale m, q şi p, separate prin câte un spaţiu.

Restricții și precizări

• 1 ≤ n ≤ 2000; 1 ≤ x ≤ 1000 ; 1 ≤ y ≤ 1000 ; 1 ≤ r ≤ 100
• dacă două cercuri, dintre cele n, au centrele în acelaşi punct din planul P, atunci razele lor sunt distincte
• două cercuri sunt exterioare dacă nu au niciun punct comun şi nici interioarele lor nu au puncte comune
• Pentru rezolvarea cerinţei a) se acordă 20% din punctaj, pentru cerinţa b) 50% din punctaj şi pentru cerinţa c) 30% din punctaj.

Exemplu:

cerc4.in

12
2 6 1
3 9 1
4 12 3
4 4 2
9 9 2
10 10 6
12 12 1
6 3 1
10 5 1
14 7 2
14 7 1
12 4 2

cerc4.out

4 3 2

Explicație

Sunt m=4 drepte distincte care conţin centrele celor 13 cercuri. Dreapta d1 trece printr-un singur centru de cerc, d4 trece prin 2 centre de cercuri exterioare.

Dreptele d2 şi d3 trec prin câte 3 centre de cercuri exterioare.

Numărul maxim de cercuri exterioare două câte două este y=3 iar centrele lor sunt situate pe d2 sau pe d3 (p=2).