Pagini recente » Cod sursa (job #1636355) | Cod sursa (job #1210380) | Cod sursa (job #424072) | Cod sursa (job #2110754) | Cod sursa (job #1721855)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<ll,ll> pll;
pll A[100100],X[100100],Y[100100];
ll N;
ll dist(pll a,pll b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
ll rez(int st,int dr){
if(st >= dr-1) return LLONG_MAX;
if(dr-st == 2) return dist(X[st],X[st+1]);
int mid = (st+dr)/2;
ll best = rez(st,mid)+rez(mid,dr);
sort(Y + st,Y + dr);
for(int i = st;i<dr-1;i++)
for(int j = i+1; j<dr-1 && j-i < 8;j++) best = min(best,dist(Y[i],Y[j]));
return best;
}
int main(){
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin >> N;
for(int i = 0;i<N;i++){cin >> A[i].x >> A[i].y; X[i] = A[i];}
sort(X,X+N);
for(int i = 0;i<N;i++) Y[i] = make_pair(X[i].y,X[i].x);
cout << fixed << setprecision(10) << sqrt(rez(0,N));
return 0;
}