cerc3

Cerc3

== include(page="template/taskheader" task_id="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, {$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.

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