Pagini recente » Cod sursa (job #1229323) | Cod sursa (job #2901384) | Cod sursa (job #186851) | Cod sursa (job #2564191) | Cod sursa (job #1026310)
#include <math.h>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
int n;
struct punct
{
int x;
int y;
}v[100010];
vector <punct> vec;
bool sortY(const punct &a, const punct &b)
{
return (a.y < b.y);
}
bool sortX(const punct &a,const punct &b)
{
return (a.x < b.x);
}
double myDistance(const punct &a1, const punct &a2)
{
double d = (double) (a1.x - a2.x) * (a1.x - a2.x) + (a1.y - a2.y) * (a1.y - a2.y) ;
d = sqrt(d);
return d;
}
double devideAndConquer(const int &left,const int &right)
{
double d;
if(right - left <= 2)
{
d = 100000000.0;
for(int i = left; i < right ; i++ )
{
for(int j = i + 1 ; j<= right; j++)
{
d = min(myDistance(v[i], v[j]),d);
}
}
sort(v+left, v + right + 1, sortY);
return d;
}
else
{
int middle = left + (right - left) / 2;
d = min(devideAndConquer(left, middle),devideAndConquer(middle + 1, right));
int l = left;
int r = middle+1;
vec.clear();
while( (l <= middle) && (r <= right) )
{
if( sortY(v[l], v[r]) == true)
{
vec.push_back(v[l]);
l++;
}
else
{
vec.push_back(v[r]);
r++;
}
}
while( l <= middle )
{
vec.push_back(v[l]);
l++;
}
while( r <= right )
{
vec.push_back(v[r]);
r++;
}
for(int i = left, k = 0; i<=right; i++,k++)
{
v[i] = vec[k];
}
for(int i = left ; i<= right ; i++)
{
for(int j = i+1; (j <= right) && (j-i < 7) ; j++)
{
d = min(myDistance(v[i],v[j]),d);
}
}
return d;
}
}
void read()
{
freopen("cmap.in", "r", stdin);
scanf("%d", &n);
for (int i = 0; i <n ; ++i)
{
scanf("%lld %lld", &(v[i].x), &(v[i].y));
}
}
void write(const double &d)
{
FILE*g = fopen("cmap.out","w");
fprintf(g, "%.6lf\n", d);
}
int main()
{
read();
sort(v ,v + n , sortX );
double d = devideAndConquer(0,n-1);
write(d);
}