Pagini recente » Cod sursa (job #3286545) | Diferente pentru implica-te/arhiva-educationala intre reviziile 193 si 223 | Cod sursa (job #3293374) | Cod sursa (job #3289570) | Cod sursa (job #378879)
Cod sursa(job #378879)
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define INF 2000000000
using namespace std;
ifstream fi("cmap.in");
int N;
struct punct { int x,y; }v[1000002];
int puncte[1000002];
int aux[1000002];
inline bool cmp(const int &x,const int &y){ return (v[x].x<v[y].x); }
inline int diffabs(int x,int y){
if (x<y) return (y-x); else return (x-y);
}
double distp(punct p1, punct p2)
{
return sqrt((double)((long long)((long long)p1.x-p2.x)*(p1.x-p2.x)+(long long)((long long)p1.y-p2.y)*(p1.y-p2.y)));
}
double dmin(int left,int right){
if (left==right) return INF;
int m=(left+right)/2;
int part=v[puncte[m]].x;
double d1=dmin(left,m),d2=dmin(m+1,right);
double minim=min(d1,d2);
int ind1=left,ind2=m+1,ind=left-1;
while (ind1<=m || ind2<=right)
if (ind1>m) { aux[++ind]=puncte[ind2];++ind2;} else
if (ind2>right) { aux[++ind]=puncte[ind1];++ind1; } else
if (v[puncte[ind1]].y<v[puncte[ind2]].y) { aux[++ind]=puncte[ind1];++ind1; }
else { aux[++ind]=puncte[ind2];++ind2; }
int np=0;
for (int i=left;i<=right;++i) {
puncte[i]=aux[i];
if ((part-(minim/2))<=v[puncte[i]].x && (part+(minim/2))>=v[puncte[i]].x) aux[++np]=puncte[i];
}
double dist=minim;
for (int i=1;i<=np;++i)
for (int j=i-1;(j>=1) && (j>=i-6);--j)
dist=min(dist,distp(v[aux[i]],v[aux[j]]));//max(diffabs(v[aux[i]].x,v[aux[j]].x),diffabs(v[aux[i]].y,v[aux[j]].y)));
return dist;
}
int main(){
fi>>N;
for (int i=1;i<=N;++i)
fi>>v[i].x>>v[i].y;
for (int i=1;i<=N;++i) puncte[i]=i;
sort(puncte+1,puncte+N+1,cmp);
double rez=dmin(1,N);
freopen("cmap.out","w",stdout);
printf("%lf\n",rez);
fi.close();
return 0;
}