Pagini recente » Cod sursa (job #1477530) | Cod sursa (job #1488630) | Cod sursa (job #908077) | Cod sursa (job #1675766) | Cod sursa (job #2069051)
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
using namespace std;
#define nmax 100099
struct punct{
long x,y;
};
typedef double ull;
punct p[nmax],aux[nmax],inter[nmax];
ull dist(punct a,punct b){
return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
bool cmp(punct a,punct b){return a.x<b.x;}
double minDist(int st,int dr){
if(dr-st+1 ==3){
if(p[st].y > p[st+1].y)swap(p[st],p[st+1]);
if(p[st+1].y > p[st+2].y)swap(p[st+1],p[st+2]);
if(p[st].y > p[st+1].y)swap(p[st],p[st+1]);
return min(dist(p[st],p[st+1]),min(dist(p[st+1],p[st+2]),dist(p[st],p[st+2])));
}if(dr-st+1 ==2){
if(p[st].y>p[st+1].y)swap(p[st],p[st+1]);
return dist(p[st],p[st+1]);
}else{
//Mai mult de 3 elemente:
int mid = (st+dr)/2;
long centru=p[mid].x;
ull delta = min(minDist(st,mid),minDist(mid+1,dr));
int r= 0;
int radDelt=sqrt(delta);
//Interclasam:
int i,j,k; i=k=st; j=mid+1;
while(i<=mid && j<=dr){
if(p[i].y < p[j].y)aux[k++]=p[i++];
else aux[k++]=p[j++];
}
while(i<=mid)aux[k++]=p[i++];
while(j<=dr) aux[k++]=p[j++];
// cout<<mid<<' '<<centru<<' '<<radDelt<<":\n";
for(i=st;i<=dr;i++){
p[i]=aux[i];
if(abs(p[i].x-centru)<= radDelt)
{inter[++r]=p[i];}
// cout<<p[i].x<<",";
}
//cout<<endl;
for(i=1;i<=r;i++)
{ j= min(r,i+7);
for(k=i+1;k<=j;k++)
delta= min(delta,dist(inter[i],inter[k]));
}
return delta;
}
}
int main(){
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n,i;
cin>>n;
for(i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
sort(p+1,p+n+1,cmp);
cout<<setprecision(6)<<fixed<<sqrt(minDist(1,n));
}