Pagini recente » Cod sursa (job #1290673) | Cod sursa (job #2235752) | Cod sursa (job #1469087) | Cod sursa (job #3191631) | Cod sursa (job #2068642)
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
#define nmax 100099
struct punct{
long double x,y;
};
typedef unsigned long long ull;
punct p[nmax],aux[nmax];
ull dist(punct a,punct b){
return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
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;
ull delta = min(minDist(st,mid),minDist(mid+1,dr));
//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++];
for(i=st;i<=dr;i++)p[i]=aux[i];
for(i=st;i<=dr;i++)
{ j= min(dr,i+7);
for(k=i+1;k<=j;k++)
delta= min(delta,dist(p[i],p[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;
cout<<setprecision(7)<<fixed<<sqrt(minDist(1,n));
}