# PBinfo #962 – Cerc4 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Se desenează n cercuri distincte în planul P, numerotate cu numerele de la 1 la n. Pentru fiecare cerc k (k∈{1,2,...,n}) se cunosc: raza cercului, rk, şi coordonatele (xk,yk) ale centrului cercului, coordonate referitoare la reperul cartezian xOy cu originea în punctul O a planului P. 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 aceasta ş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:
a) numărul m de drepte distincte; 
b) 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; 
c) 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 cerc4.in conține pe prima linie numărul n de cercuri, iar pe următoarele n linii câte trei numere x y r, reprezentând coordonatele centrului și raza fiecărui cerc.

Date de ieșire
Fișierul de ieșire cerc4.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 și precizări

1 ≤ n ≤ 2000; 1 ≤ x ≤ 1000 ; 1 ≤ y ≤ 1000 ; 1 ≤ r ≤ 100
dacă două cercuri, dintre cele n, au centrele în acelaşi punct din planul P, 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 cerinţei a) se acordă 20% din punctaj, pentru cerinţa b) 50% din punctaj şi pentru cerinţa c) 30% din punctaj.

Exemplu:
cerc4.in

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

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

## Cod sursă C++

```cpp
/*prof. Carmen Minca. Liceul "Ion Neculce" Bucuresti
  Sursa 100p. Reducerea fiecarui cerc la intervalul intersectiei acestuia cu dreapta pe care se afla centru sau.
  Problema se reduce la a determina pt fiecare dreapta numarul maxim de intervale disjuncte doua cate doua
  sursa e bazata pe o rezolvare gen problema spectacolelor (greedy)*/
#include <cstdio>
#include <cmath>
struct cerc
  {int x,y,r,d,e; double a,b;};
cerc c[2001];
int n,nr;
int x[2001];
FILE *f,*g;
int ver_dr(cerc p, cerc q)
{ return (((long)p.x*q.y)==((long)p.y*q.x));}
void citire()
{                                      //citire date+ crearea lui X si Y
  f=fopen("cerc4.in","r");
  fscanf(f,"%d",&n);
  int i; double d;
  for(i=1;i<=n;i++)
{ fscanf(f,"%d%d%d",&c[i].x,&c[i].y,&c[i].r);
  c[i].e=1;  c[i].d=0;
  d=sqrt(pow(c[i].x,2)+pow(c[i].y,2));
  c[i].a=d-c[i].r;
  c[i].b=d+c[i].r;
}
  fclose(f);
}
int poz(int i,int j)
{ int m=-1, ind; cerc s;
  while(i<j)
  { ind=0;
    if((c[i].b>c[j].b)||(c[i].b==c[j].b)&&(c[i].a>c[j].a))
     {ind =1; s=c[i]; c[i]=c[j]; c[j]=s;}
    if(ind)
     {if(m==-1)i++;
	else j--;
      m=-m;
     }
     else
      if(m==-1)j--;
	else i++;
  }
  return i;
}
void dv(int s, int d)   //sortez crescator cercurile dupa capatul din dreapta prin Qsort
{ if(d>s)
   {int k;
    k=poz(s,d);
    dv(s,k-1);dv(k+1,d);}
}
void drepte()
{int i,p,j;
 for(i=1;i<=n;i++)
  if(c[i].d==0)
   {nr++; c[i].d=nr; p=1;
    for(j=i+1;j<=n;j++)
     if((c[j].d==0)&&ver_dr(c[i],c[j]))
	{c[j].d=nr;p++;}
    x[nr]=p;
    }
}
int main()
{ citire();
  dv(1,n);
  int p,max=1,i,j,k,t=1;
  drepte();
  for(p=1;p<=nr;p++)
  {
   for(i=1;i<=n;i++)
   if(c[i].d==p)
   { k=1;
     j=i+1;
     while(j<=n)
      { if((p==c[j].d)&&(c[i].b<c[j].a))
         {k++;i=j;}
       j++;
      }
     if(max<k){max=k;t=1;}
       else if(max==k)t++;
   }
  }
  g=fopen("cerc4.out","w");
  fprintf(g,"%d %d %d",nr,max,t);
  fclose(g);
return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/962)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/962/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-962/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)