== include(page="template/taskheader" task_id="cerc3") ==
Poveste şi cerinţă...
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, {$r{~k~}$}, şi coodonatele ({$x{~k~}$}, {$y{~k~}$}) 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.
h2. 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ă.
h2. Date de intrare
Fişierul de intrare $cerc3.in$ ...
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 ({$x{~k~}$},{$y{~k~}$}) şi raza {$r{~k~}$} ale celui de-al $k$-lea cerc.
h2. Date de ieşire
În fişierul de ieşire $cerc3.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 2000$
* $1 ≤ x{~1~}, x{~2~}, ..., x{~n~} ≤ 1000$
* $1 ≤ y{~1~}, y{~2~}, ..., y{~n~} ≤ 1000$
* $1 ≤ r{~1~}, r{~2~}, ..., r{~n~} ≤ 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.
h2. Exemplu
table(example). |_. cerc3.in |_. cerc3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
!>problema/cerc3?cerc.JPG 200x200!
Sunt $m=4$ drepte distincte care conţin centrele celor $12$ cercuri. Dreapta {$d{~1~}$} trece printr-un singur centru de cerc, {$d{~4~}$} trece prin $2$ centre de cercuri exterioare. Dreptele {$d{~2~}$} şi {$d{~3~}$} 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 {$d{~2~}$} sau pe {$d{~3~}$} ({$p=2$}).
== include(page="template/taskfooter" task_id="cerc3") ==
