Pagini recente » Cod sursa (job #1906015) | Cod sursa (job #2637085) | Cod sursa (job #1111694) | Cod sursa (job #1661202) | Cod sursa (job #1982203)
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
#define ll long long
#define pb push_back
const int NMax = 1e5 + 5;
const ll inf = 2e18 + 5;
int N;
struct elem {
int x,y;
elem(int _x = 0,int _y = 0) {
x = _x;
y = _y;
}
}v[NMax],aux[NMax];
bool operator <(elem a,elem b) {
return a.y < b.y;
}
bool cmp(elem a,elem b) {
return a.x < b.x;
}
ll solve(int,int);
ll dist(elem,elem);
int main() {
in>>N;
for (int i=1;i <= N;++i) {
int x,y;
in>>x>>y;
v[i] = elem(x,y);
}
sort(v +1,v +N+1,cmp);
out<<fixed<<setprecision(6)<<sqrt(solve(1,N))<<'\n';
in.close();out.close();
return 0;
}
ll solve(int st,int dr) {
if (st == dr) {
return inf;
}
else if (dr - st + 1 == 2) {
if (v[dr] < v[st]) {
swap(v[st],v[dr]);
}
return dist(v[st],v[dr]);
}
int mij = (st+dr)/2,
abscisa = v[mij].x,
nrAux = (dr-st+1);
ll mn = min(solve(st,mij),solve(mij+1,dr));
merge(v+st,
v+mij+1,
v+mij+1,
v+dr+1,
aux+1);
nrAux = 0;
for (int i=st;i <= dr;++i) {
v[i] = aux[++nrAux];
}
nrAux = 0;
double root = sqrt(mn);
for (int i=st;i <= dr;++i) {
if (abs(v[i].x - abscisa) <= root) {
aux[++nrAux] = v[i];
}
}
for (int i=1;i <= nrAux;++i) {
for (int j=i+1;j <= nrAux && j-i+1 <= 8;++j) {
mn = min(mn,dist(aux[i],aux[j]));
}
}
return mn;
}
ll dist(elem a,elem b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}