Pagini recente » Cod sursa (job #2209038) | Cod sursa (job #2839732) | Cod sursa (job #2204279) | Cod sursa (job #1728473) | Cod sursa (job #1860185)
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <stack>
#include <bitset>
#include <cctype>
#include <set>
#define MOD 9973
#define pb push_back
#define INF 0x3f3f3f3f
#define INFLL (1LL*INF*INF)
#define ll long long
#define NMAX 100005
using namespace std;
typedef pair<ll, ll> pii;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pii p[NMAX],aux[NMAX];
int n;
inline double dist(pii a, pii b) {
return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}
bool compy(pii a, pii b) {return a.second<b.second;}
pii jeg[NMAX];
double solve(int st, int dr) {
cout<<"jeg";
if(dr-st<=1) return INF;
if(dr-st==2) {
if(aux[st].second>aux[st+1].second) swap(aux[st],aux[st+1]);
cout<<"vasi";
return dist(p[st],p[st+1]);
}
else if(dr-st==3) {
sort(aux+st,aux+dr,compy);
cout<<"vasi";
return min(dist(p[st],p[st+1]),min(dist(p[st],p[st+2]),dist(p[st+2],p[st+1])));
}
int mid=(st+dr)/2,i,j,pos=st,ind1,ind2;
double delta=solve(st, mid);
delta=min(delta,solve(mid, dr));
merge(aux,aux+mid,aux+mid,aux+dr,jeg+st);
for(i=st;i<dr;++i) aux[i]=jeg[i];
vector<pii> v;
for(i=st;i<dr;++i)
if(abs(aux[i].first-p[mid].first)<=delta) v.pb(aux[i]);
for(i=0;i<v.size();++i)
for(j=i+1;j<v.size()&&j-i<8;++j)
delta=min(delta,dist(v[i],v[j]));
return delta;
}
int main() {
int i;
fin>>n;
for(i=1;i<=n;++i) fin>>p[i].first>>p[i].second;
sort(p+1,p+n+1);
for(i=1;i<=n;++i) aux[i]=p[i];
fout<<fixed<<setprecision(6)<<solve(1,n+1);
return 0;
}