Rezolvare completă PbInfo #841 Bomber

Cerința

Se consideră un poligon militar, pe care este stabilit un sistem de axe de coordonate xOy. Se dau n bombe, numerotate de la 1 la n, pentru fiecare cunoscându-se coordonatele x y și puterea de distrugere p. La explozia unei bombe de putere p se va distruge totul în interiorul și pe cercul de centru x y și rază p, iar dacă există alte bombe în această zonă, vor exploda la rândul lor.

Dându-se numărul de ordine I al unei bombe care explodează, să se determine câte bombe rămân intacte la finalul șirului de explozii declanșate.

Date de intrare

Fișierul de intrare bomber.in conține pe prima linie numerele n I, fiecare dintre următoarele n linii conține câte trei numere x y p, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire bomber.out va conține pe prima linie numărul C, reprezentând numărul de bombe rămase neexplodate.

Restricții și precizări

  • 1 ≤ n ≤ 100
  • 1 ≤ I ≤ n
  • coordonatele x y sunt numere întregi, iar puterile p sunt numere naturale
  • -200 ≤ x , y ≤ 200
  • * 1 ≤ p ≤ 30

Exemplu

bomber.in

9 5
0 3 2
-1 1 3
1 4 1
3 4 4
-1 -2 3
3 1 3
0 -4 2
3 -2 5
4 -1 2

bomber.out

4

Explicație

Bombele sunt dispuse ca în desen:

Mai întâi va exploda bomba colorată cu verde, apoi cele colorate cu roșu, apoi cea colorată cu mov, apoi cea colorată cu negru.

Cele 4 bombe colorate cu albastru nu vor exploda.

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

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("bomber.in");
ofstream fout("bomber.out");

int n , m , v[105] , x[105] , y[105] , p[105] , start;

void explozie(int k)
{
    v[k] = 1;
    for(int i = 1 ; i <= n ; i ++)
        if(v[i] == 0 && (x[i] - x[k])*(x[i] - x[k]) + (y[i] - y[k])*(y[i] - y[k]) <= p[k] * p[k] )
            explozie(i);
}

int main(){
    fin >> n >> start;
    for(int i = 1 ; i <= n ; i ++)
            fin >> x[i] >> y[i] >> p[i];
    fin.close();
    
    explozie(start);
    
    int cnt = 0;
    for( int i = 1; i <= n ; i ++)
        if(v[i] == 0)
            cnt ++;
    fout << cnt;
    fout.close();
    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 #841 Bomber

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