Pagini recente » Cod sursa (job #922876) | Cod sursa (job #349002) | Cod sursa (job #27021) | Cod sursa (job #3250320) | Cod sursa (job #1804041)
#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;
}