cerc3

Cerc3

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. 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;

* $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 cerinţă $50%$ din punctaj şi pentru a treia cerinţă $30%$ din punctaj.

* 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

h3. Explicaţie

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$ ).
 

!>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") ==

3922