Pagini recente » Cod sursa (job #18790) | Cod sursa (job #1906600) | Cod sursa (job #604012) | Cod sursa (job #1705394) | Cod sursa (job #1257610)
#include <fstream>
#include <cstdlib>
#include <math.h>
using namespace std;
ifstream x ("cmap.in");
ofstream y ("cmap.out");
struct coordinates
{float x;
float y;
};
int i,n;
coordinates points[100010];
void read()
{x>>n;
n=0;
while(x>>points[++n].x && x>>points[n].y);
n=n-1;
/*Test if we read correctly
for(i=1;i<=n;i++)
y<<points[i].x<<" "<<points[i].y<<"\n";
*/
}
float quicksort_x (coordinates v[], int l, int r)
{if(l>=r)
return 1;
int poz,pivot,i,j;
coordinates aux;
poz=rand()%(r-l)+l+1;
aux=v[l];
v[l]=v[poz];
v[poz]=aux;
pivot=v[l].x;
poz=l;
i=l+1;
for(j=l+1;j<=r;j++)
if(v[j].x<pivot)
{aux=v[j];
v[j]=v[i];
v[i]=aux;
i++;
/*
int k;
y<<j<<" --> ";
for(k=1;k<=n;k++)
y<<v[k].x<<" ";
y<<'\n';
*/
}
aux=v[poz];
v[poz]=v[i-1];
v[i-1]=aux;
quicksort_x(v,l,i-2);
quicksort_x(v,i,r);
}
float distance(float ax, float ay, float bx, float by)
{float d1,d2,d;
d1=ax-bx;
d2=ay-by;
d=sqrt(d1*d1+d2*d2);
return d;
}
float closest_pair(coordinates v[],int n)
{if(n<=1)
return 999999999;
if(n==2)
return distance(v[1].x, v[1].y, v[2].x, v[2].y);
int n1=0,n2=0;
float dist,DLmin,DRmin;
coordinates v1[n/2+2],v2[n/2+2];
for(i=1;i<=n;i++)
if(i<=n/2)
v1[++n1]=v[i];
else
v2[++n2]=v[i];
DLmin=closest_pair(v1,n1);
DRmin=closest_pair(v2,n2);
dist=min(DLmin,DRmin);
//trial #2
float l1,l2,d,minn;
int c1,c2;
l1=v1[n1].x-dist;
l2=v2[1].x+dist;
minn=dist;
for(c1=1;c1<=n1;c1++)
if(v1[c1].x>=l1)
for(c2=1;c2<=n2;c2++)
if(v2[c2].x<=l2)
{d=distance(v1[c1].x, v1[c1].y, v2[c2].x, v2[c2].y);
if(d<minn)
minn=d;
}
//end trial #2
return min(dist,minn);
}
int main()
{read();
quicksort_x(points,1,n);
/*//Test if sort is working properly
for(i=1;i<=n;i++)
y<<points[i].x<<" "<<points[i].y<<"\n";
*/
y<<closest_pair(points,n);
}
//1761.154735