Pagini recente » Cod sursa (job #1257135) | Cod sursa (job #2418804) | Cod sursa (job #1640075) | Cod sursa (job #1962010) | Cod sursa (job #2492661)
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>
using namespace std;
struct punct{
long long x,y;
};
vector <punct> P;
long long length(punct a,punct b){
long long rv;
rv=( 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y) );
return rv;
}
bool cmpP(punct a,punct b){
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
bool cmpPY(punct a,punct b){
if(a.y!=b.y)
return a.y<b.y;
else
return a.x<b.x;
}
long long rec(long long s,long long d){
if(d-s<2)
return INT_MAX;
if(d-s==2)
return length(P[d],P[s]);
long long mid=(s+d)/2;
long long r=min(rec(s,mid),rec(mid,d));
if(d-s>2){
vector <punct> Y;
punct aux;
long long x;
for(long long i=s;i<d;i++){
aux.x=P[mid].x;
aux.y=P[i].y;
x=length(P[i],aux);
if(x<r)
Y.push_back(P[i]);
}
sort(Y.begin(),Y.end(),cmpPY);
long long MIN=r;
for(long long i=0;i<Y.size();i++){
for(long long j=i+1;j<=i+7 && j<Y.size();j++){
x=length(Y[i],Y[j]);
if(x<MIN)
MIN=x;
}
}
return MIN;
}
else
return r;
}
int main()
{
ifstream in("cmap.in");
ofstream out("cmap.out");
long long n;
in>>n;
punct aux;
for(long long i=1;i<=n;i++){
in>>aux.x>>aux.y;
P.push_back(aux);
}
sort(P.begin(),P.end(),cmpP);
long long s=0,d=n-1;
long long r=rec(s,d);
out<<setprecision(8)<<sqrt(r);
return 0;
}