Pagini recente » Cod sursa (job #1162040) | Cod sursa (job #1292231) | Cod sursa (job #1755178) | Cod sursa (job #1127945) | Cod sursa (job #1687436)
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <climits>
using namespace std;
struct punct{
int x, y;
};
punct v[100000];
bool sort_by_x(punct a, punct b){
if(a.x>b.x)return true;
else return false;
}
double dist(punct a, punct b){
return sqrt(((double)a.x-(double)b.x)*((double)a.x-(double)b.x)+((double)a.y-(double)b.y)*((double)a.y-(double)b.y));
}
double solve_s(punct* s, punct* m, punct* e, double min_dst){
while(m->x - s->x > min_dst)s++;
while(e->x - m->x > min_dst)e--;
for(;s<e;s++){
for(int i=1;i<7&&i+s<e;i++){
double t=dist(*s, *(s+i));
if(t<min_dst){
min_dst=t;
}
}
}
return min_dst;
}
double solve(punct* s, punct* e){
double minim=INT_MAX;
if(e-s<=3){
for(punct* it0=s;it0<e;it0++){
for(punct* it1=it0+1;it1<e;it1++){
double t=dist(*it0, *it1);
if(t<minim){
minim=t;
}
}
}
return minim;
}
return solve_s(s, s+((e-s)/2), e, min(solve(s, s+((e-s)/2)),solve(s+((e-s)/2), e)));
}
int main()
{
FILE* f=fopen("cmap.in", "r");
int n;
fscanf(f, "%d", &n);
for(int i=0;i<n;i++)
fscanf(f, "%d %d", &v[i].x, &v[i].y);
sort(v, v+n, sort_by_x);
fclose(f);
f=fopen("cmap.out", "w");
fprintf(f, "%f", solve(v, v+n));
return 0;
}