Fişierul intrare/ieşire:cerc3.in, cerc3.outSursăOJI 2009, clasele 11-12
AutorCarmen MincaAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.025 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cerc3

Se desenează n cercuri distincte în plan, numerotate cu numerele de la 1 la n. Pentru fiecare cerc k ( 1 ≤ k ≤ n ) se cunosc: raza cercului, rk, şi coodonatele (xk, yk) ale centrului cercului, coordonate referitoare la reperul cartezian xOy cu originea în punctul O din plan. 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 această dreaptă ş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:

  • Numărul m de drepte distincte;
  • 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;
  • 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 cerc3.in conţine pe prima linie, o valoare naturală nenulă n, reprezentând numărul de cercuri. Următoarele n linii conţin câte trei numere naturale nenule, separate prin câte un spaţiu, care reprezintă coordonatele centrului (xk,yk) şi raza rk ale celui de-al k-lea cerc.

Date de ieşire

Fişierul de ieşire cerc3.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

  • 1 ≤ n ≤ 2000
  • 1 ≤ x1, x2, ..., xn ≤ 1000
  • 1 ≤ y1, y2, ..., yn ≤ 1000
  • 1 ≤ r1, r2, ..., rn ≤ 70
  • Dacă două cercuri, dintre cele n, au centrele în acelaşi punct din plan, 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 primei cerinţei se acordă 20% din punctaj, pentru a doua cerinţă 50% din punctaj şi pentru a treia cerinţă 30% din punctaj.

Exemplu

cerc3.incerc3.out
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
4 3 2

Explicaţie


Sunt m=4 drepte distincte care conţin centrele celor 12 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 q=3 iar centrele lor sunt situate pe d2 sau pe d3 (p=2).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content