Pagini recente » Cod sursa (job #1273554) | Cod sursa (job #1876109) | Statisticile problemei Ecuatie | Cod sursa (job #1255068) | Cod sursa (job #2073501)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;
template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}
struct point{
ll x,y;
point(ll x=0, ll y=0) : x(x), y(y) {}
};
ld dist(point A, point B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int N; point a[100100];
ld mind(int l, int r){
if (r-l+1<=1) return (1LL<<50);
if (r-l+1==2){
if (a[l].y>a[r].y) swap(a[l],a[r]);
return dist(a[l],a[r]);
}
ld ans=(1LL<<50);
int mid=(l+r)/2;
ans=min(ans,mind(l,mid));
ans=min(ans,mind(mid+1,r));
vector<point> v;
int x=l,y=mid+1;
while (x<=mid && y<=r){
if (a[x].y<a[y].y) v.pb(a[x]),x++;
else v.pb(a[y]),y++;
}
while (x<=mid) v.pb(a[x]),x++;
while (y<=r) v.pb(a[y]),y++;
int i,j;
for (i=l; i<=r; i++)
a[i]=v[i-l];
for (i=l; i<=r; i++)
for (j=i+1; j<=r && j-i<=8; j++)
ans=min(ans,dist(a[i],a[j]));
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ifstream fin("cmap.in");
ofstream fout("cmap.out");
fin >> N;
int i;
for (i=1; i<=N; i++)
fin >> a[i].x >> a[i].y;
sort(a+1,a+N+1,[](point A, point B){return A.x<B.x; });
fout << fixed << setprecision(10) << mind(1,N) << "\n";
return 0;
}