Cod sursa(job #1740451)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 11 august 2016 16:45:48
Problema Generare de permutari Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define N 205

using namespace std;

int n,p[N];
vector < int > G[N];
queue < int > Q;

struct val
{
int x,y,z,r;
} v[N];


void read()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d",&v[i].x,&v[i].y,&v[i].z,&v[i].r);
}

void solve()
{
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(v[i].z>v[j].z)
        { if((v[i].r+v[j].r)>=sqrt((v[j].y-v[i].y)*(v[j].y-v[i].y)+(v[j].x-v[i].x)*(v[j].x-v[i].x)))
            G[i].push_back(j);
        }

}

int nr=1;

void BFS()
{
    Q.push(1);
    p[1]=1;
    vector<int>::iterator it;
    while(!Q.empty())
    {int b=Q.front();
        Q.pop();

    for(it = G[b].begin();it!=G[b].end();++it)
    {
        if(p[*it]==0)
        {
            p[*it]=1;
            Q.push(*it);
            nr++;
        }
    }
    }

}

int main()
{
    freopen("mere.in", "r", stdin);
    freopen("mere.out", "w", stdout);
    read();
    solve();
    BFS();
    printf("%d",nr);
    return 0;
}