| Fişierul intrare/ieşire: | cerc3.in, cerc3.out | Sursă | OJI 2009, clasele 11-12 |
| Autor | Carmen Minca | Adăugată de |  Gabriel Bitis •gabitzish1 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | cerc3.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).
