Pagini recente » Cod sursa (job #367923) | Cod sursa (job #1353384) | Cod sursa (job #3158220) | Cod sursa (job #2011675) | Cod sursa (job #2275169)
#include <stdio.h>
#include <algorithm>
#include <math.h>
const int dmax = 100000;
unsigned const int INF = (1ULL << 32) - 1;
struct point
{
long long x,y;
};
point pointsX[dmax];
point pointsY[dmax];
point pointsL[dmax];
bool cmpX(point a, point b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool cmpY(point a, point b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double distance(point a, point b)
{
return sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
}
double min_dist(int first, int last, int n)
{
double best_distance = INF;
double dist;
int point_nr, mid, i, j;
///cazuri oprire
point_nr = last - first + 1;
if (point_nr == 1)
return best_distance;
if (point_nr == 2)
return distance(pointsY[first],pointsY[last]);
///divide
mid = first + (last - first)/2;
best_distance = std::min(min_dist(first,mid,n), min_dist(mid+1,last,n));
///combina
int u_bound = pointsY[mid].y + (int)best_distance;
int l_bound = pointsY[mid].y - (int)best_distance;
int Lsize = 0;
for (i = 0; i < n; i++)
if (l_bound <= pointsX[i].y && pointsX[i].y <= u_bound)
pointsL[Lsize++] = pointsX[i];
for (i = 0; i < Lsize - 1; i++)
{
j = i + 1;
int count = 1;
while (j < Lsize && count < 8)
{
dist = distance(pointsL[i],pointsL[j]);
if (dist < best_distance)
best_distance = dist;
count++;
j++;
}
}
return best_distance;
}
int main()
{
FILE *f;
int i,n;
f=fopen("cmap.in","r");
fscanf(f,"%d",&n);
for (i=0; i<n; i++)
{
fscanf(f,"%lld%lld",&pointsX[i].x,&pointsX[i].y);
pointsY[i]=pointsX[i];
}
fclose(f);
std::sort(pointsX,pointsX+n,cmpX);
std::sort(pointsY,pointsY+n,cmpY);
double ans = min_dist(0,n - 1,n);
f=fopen("cmap.out","w");
fprintf(f,"%f",ans);
fclose(f);
return 0;
}