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, r_k, şi coordonatele (x_k,y_k) 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

cerc4.out

4 3 2

Explicație

Sunt m=4 drepte distincte care conţin centrele celor 13 cercuri. Dreapta d₁ trece printr-un singur centru de cerc, d₄ trece prin 2 centre de cercuri exterioare.

Dreptele d₂ şi d₃ 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 d₂ sau pe d₃ (p=2).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Cerc4:

/*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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #962 Cerc4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #962 Cerc4 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #962 Cerc4