Pagini recente » Cod sursa (job #1130374) | Cod sursa (job #991774) | Cod sursa (job #22090) | Cod sursa (job #1917468) | Cod sursa (job #2170546)
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#define pii pair<int,int>
#define Nmax 100002
#define ld long double
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
pii P[Nmax];
bool comp(pii a,pii b){if (a.first==b.first) return a.second<b.second; return a.first<b.first;}
ld dist(pii a,pii b){
return sqrt(1LL * (a.first-b.first) * (a.first-b.first) + 1LL * (a.second-b.second) * (a.second-b.second));
}
ld solve(int st,int dr){
ld mn = 1e13;
if (st==dr) return 1e13;
if (st+1==dr) return dist(P[st],P[dr]);
int mid = (st+dr)/2;
mn = min(solve(st,mid),solve(mid+1,dr));
vector<pii> L,R;
ld VMID = (P[mid].first+P[mid+1].first)/2;
for(int i=mid;i>=st && abs(VMID-P[i].first)<=mn;i--) L.push_back(P[i]);
for(int i=mid+1;i<=dr && abs(VMID-P[i].first)<=mn;i++) R.push_back(P[i]);
sort(L.begin(),L.end(),comp);
sort(R.begin(),R.end(),comp);
int a = 0,b = 0;
while (a<L.size() && b<R.size()){
mn = min(mn,dist(L[a],R[b]));
if (L[a]<=R[b]){
if (b+1<R.size()) mn = min(mn,dist(L[a],R[b]));
a++;
}
else{
if (a+1<L.size()) mn = min(mn,dist(L[a],R[b]));
b++;
}
}
return mn;
}
int main()
{
f>>n;
for (int i=1;i<=n;i++) f>>P[i].first>>P[i].second;
sort(P+1,P+n+1,comp);
g<<fixed<<setprecision(12)<<solve(1,n);
return 0;
}