Pagini recente » Cod sursa (job #2400580) | Cod sursa (job #1268032) | Cod sursa (job #3198664) | Cod sursa (job #1180895) | Cod sursa (job #792134)
Cod sursa(job #792134)
#include<fstream>
#include<math.h>
using namespace std;
#define MAXN 100100
int n, nrc, a[400][400], st[MAXN],i;
double x[MAXN], y[MAXN],dx,dy,xmin,ymin,xmax, ymax, dmin;
int ultim(int nod) {
while (st[nod])
nod=st[nod];
return nod;}
void parcurg(int nod){
double d;
do
{d=sqrt(pow(x[i]-x[nod],2)+pow(y[i]-y[nod],2) );
if (d<dmin && nod!=i) dmin=d;
nod=st[nod];}
while (st[nod]); }
int main(){
ifstream f1("cmap.in");
ofstream f2("cmap.out");
f1>>n;
for (i=1; i<=n; i++)
f1>>x[i]>>y[i];
nrc=sqrt(n)+1;
ymin=ymax=y[1];
xmin=xmax=x[1];
for (i=1;i<=n; i++)
{ if (x[i]>xmax) xmax=x[i];
else if (x[i]<xmin) xmin=x[i];
if (y[i]>ymax) ymax=y[i];
else if (y[i]<ymin) ymin=y[i]; };
dx=(xmax-xmin)/nrc;
dy=(ymax-ymin)/nrc;
for (i=1; i<=n; i++)
{ int zonax= (x[i]-xmin)/dx+1;
int zonay= (y[i]-ymin)/dy+1;
if (a[zonax][zonay] ==0) a[zonax][zonay]=i;
else st[ultim(a[zonax][zonay])]=i; };
int j,k;
dmin=sqrt(pow(x[1]-x[2],2)+pow(y[1]-y[2],2));
for (i=1; i<=n; i++)
for (j=(x[i]-xmin)/dx; j<=(x[i]-xmin)/dx+2; j++)
for (k=(y[i]-ymin)/dx; k<=(y[i]-ymin)/dy+2; k++)
if (a[j][k]) parcurg(a[j][k]);
f2<<dmin;
f1.close();
f2.close();
return 0;
}