Cod sursa(job #1804041)

Utilizator alin1999Buzatu Alin alin1999 Data 12 noiembrie 2016 10:17:25
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
float x[1001],y[1001],b[1001][1001],d1,d2,d3;
int a[1001][1001],i,j,prim,ultim,varf,nr,c[1001],n;
bool ok[1001],viz[1001],ok1;
void bfs()
{
    int k;
    while(prim<=ultim)
    {
        varf=c[prim];
        for(k=1;k<=n;k++)
            if(a[varf][k]==1&&viz[k]==0)
        {
            ultim++;
            c[ultim]=k;
            viz[k]=1;
        }
        prim++;
    }
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>x[i]>>y[i];
   for(i=1;i<=n;i++)
       for(j=i+1;j<=n;j++)
    {d1=sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
    if(d1)
    b[i][j]=d1;}
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        for(int t=1;t<=n;t++)
        for(int m=j+1;m<=n;m++)
        if(b[i][j]==b[t][m])
    {
        a[i][j]=a[j][i]=1;
        a[t][m]=a[m][t]=1;
        a[i][t]=a[t][i]=1;
    }
        for(i=1;i<=n;i++)
        {ok1=0;
            for(j=1;j<=n;j++)
            if(a[i][j]==1)
            ok1=1;
            if(ok1)
                ok[i]=1;}
            for(i=1;i<=n;i++)
                {if(viz[i]==0 && ok[i]==1)
            {prim=ultim=1;
                viz[i]=1;c[prim]=i;
                bfs();nr++;}
            for(j=1;j<=ultim;j++)
                c[j]=0;}
fout<<nr;
return 0;

}