Rezolvare completă PbInfo #950 Cerc3

Se consideră pe axa Ox din plan n puncte distincte reprezentând centrele a n cercuri numerotate cu numerele distincte de la 1 la n. Pentru fiecare cerc k se cunosc abscisa xk a centrului său şi raza sa rk.

Cerința

Să se scrie un program care să determine numărul y maxim de cercuri exterioare două câte două dintre cele n.

Date de intrare

Fișierul de intrare cerc3.in conține pe prima linie pe prima linie, o valoare naturală n, reprezentând numărul de cercuri, iar pe următoarele n linii câte două numere naturale, separate printr-un spaţiu, care reprezintă abscisa x1 a centrului primului cerc şi raza sa r1,…, abscisa xn a centrului celui de-al n-lea cerc şi raza sa rn.

Date de ieșire

Fișierul de ieșire cerc3.out va conține o linie pe care va fi scris numărul natural y reprezentând numărul maxim de cercuri exterioare ale căror centre sunt situate pe axa Ox.

Restricții și precizări

  • numerele n, x1,x2,…,xn, r1, r2,…, rn sunt numere naturale
  • 1 ≤ n ≤ 300
  • 1 ≤ x1,x2,…,xn ≤ 150
  • 1 ≤ r1, r2,…, rn ≤ 70
  • dacă două cercuri, dintre cele n, au centrele în acelaşi punct de pe axa Ox, atunci razele lor sunt distincte
  • două cercuri sunt exterioare dacă nu au niciun punct comun şi nici interioarele lor nu au puncte comune

Exemplu

cerc3.in

8
3 1
1 4
8 1
11 2
15 2
16 6
21 2
21 1

cerc3.out

4

Explicație

Numărul maxim de cercuri exterioare două câte două este y=4. De exemplu, pot fi alese cele 4 cercuri colorate din imaginea de mai jos.

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 Cerc3:

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("cerc3.in");
ofstream g ("cerc3.out");
int n;
struct cerc
{
    int a, b;
};
cerc v[310];
void citire ()
{
    f>>n;
    int r, o;
    for (int i=1; i<=n; i++)
    {
        f>>o>>r;
        v[i].a=o-r;
        v[i].b=o+r;
    }
}
bool comp (cerc x, cerc y)
{
    return x.b<y.b;
}
void rez ()
{
    int x, nr=1;
    x=v[1].b;
    for (int i=1; i<n; i++)
    {
        if (x<v[i+1].a)
        {
            nr++;
            x=v[i+1].b;
        }
    }
    g<<nr;
}
int main ()
{
    citire ();
    sort (v+1, v+n+1, comp);
   // for (int i=1; i<=n; i++) cout<<v[i].a<<<<v[i].b<<endl;
    rez ();
    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 #950 Cerc3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #950 Cerc3 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!