Question

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

Answer 1

Ecuatia generala a unei drepte este y=m*x+b unde (x,y) sunt coordonatele unui punct de pe dreapta, m este panta dreptei si b este deplasarea dreptei fata de origine.
Cum la noi scrie ca toate dreptele trec prin originea planului O(0,0) atunci punctul respectiv apartine tuturor dreptelor cu formula de mai sus adica pentru x=0 si y=0 aven atunci
0=m*0+b adica b=0
Deci deplasarea va fi intotdeauna 0, inseamna ca ecuatia dreptei va deveni
y=m*x. Deci dreptele sunt definite doar prin panta lor m.

Putem face 2 structuri
1) Structura cercului care sa contina coordonatele centrului cercului (x,y) si raza r
2) Structura dreptei care contine: panta dreptei, lista de structuri de cerc care au centrul cercului pe acea dreapta, si numarul de centre de pe dreapta

2 cercuri exterioare nu trebuie sa se atinga sau sa se suprapuna unul pe celalalt. Stim ca dreptele unesc centrele a doua cercuri. Deci o dreapta va contine in mod automat si razele individuale ale celor doua cercuri. Sa zicem ca avem cercurile cu razele r1,r2 si distanta d dintre cercuri. Avem urmatoarele situatii
a) Cercuri suprapuse: r1+r2>d
b) Cercuri tangente: r1+r2=d
c) Cercuri exterioare r1+r2<d

Deci noi o sa verificam conditia c)
Programul pe care l-am scris este mai degraba educativ si nu va aduce punctaj mare. Am adaugat si linii care sa iti afiseze niste pasi intermediari. Sper sa te ajute

8f2bbf5155f1611fb1a8fbde582bc91e.cpp

Answer 2

#include <bits/stdc++.h>
#define maxN 2004 //nimeni altu
using namespace std;
const int INF=(1<<30);
struct point
{
    double x,y,r;
    double _tan;
    double first,last;
}v[maxN];
bool cmp(const point &a,const point &b)
{
    if(a._tan==b._tan)
        return a.last<b.last;
    return a._tan<b._tan;
}
int n,i,j,lines=1,maxc,currc,nr,ind;
int main()
{
    freopen("cerc4.in","r",stdin);
    freopen("cerc4.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lf %lf %lf",&v[i].x,&v[i].y,&v[i].r);
    for(i=1;i<=n;i++)
        if(v[i].y!=0)
            v[i]._tan=v[i].x/v[i].y;
        else v[i]._tan=INF;
    for(i=1;i<=n;i++)
    {
        double aux=sqrt(v[i].x*v[i].x+v[i].y*v[i].y);
        v[i].first=aux-v[i].r;
        v[i].last=aux+v[i].r;
    }
    sort(v+1,v+n+1,cmp);
    maxc=1,nr=1,currc=1,ind=1;
    for(i=2;i<=n;i++)
    {
        if(v[i]._tan!=v[i-1]._tan)
        {
            lines++;
            currc=1;
            if(maxc==currc)
                nr++;
            ind=i;
        }
        else if(v[i].first>v[ind].last)
        {
            currc++;
            if(currc>maxc)
                maxc=currc,nr=1;
            else if(currc==maxc)
                nr++;
            ind=i;
        }
    }
    printf("%d %d %d",lines,maxc,nr);
    return 0;
}