Pagini recente » Cod sursa (job #2054944) | Cod sursa (job #2024165) | Cod sursa (job #2277564) | Cod sursa (job #1750697) | Cod sursa (job #2138032)
#include <bits/stdc++.h>
#define point pair< double, double >
#define x first
#define y second
FILE *fin = freopen("cmap.in", "r", stdin);
FILE *fout = freopen("cmap.out", "w", stdout);
using namespace std;
/*---------Data--------*/
const int MAX = 1e5 + 2;
const int INF = 2e9 + 2;
int n;
point p[MAX];
struct comp{
bool operator () (const int &a, const int &b) const{
return p[a].y < p[b].y;
}
};
void Read(){
scanf("%d", &n);
for(int i = 0; i < n; ++ i)
scanf("%lf%lf", &p[i].x, &p[i].y);
}
double Dist(point p1, point p2){
return sqrt(1LL * (p1.y - p2.y) * (p1.y - p2.y) +
1LL * (p1.x - p2.x) * (p1.x - p2.x));
}
double StripClosest(int strip[], int len, double d){
double ans = d;
sort(strip, strip + len, comp());
for(int i = 0; i < len; ++ i){
point p1 = p[strip[i]];
for(int j = i + 1; j < len; ++ j){
point p2 = p[strip[j]];
if((p2.y - p1.y) >= d) break;
ans = min(ans, Dist(p1, p2));
}
}
return ans;
}
double BruteForce(int left, int right){
double ans = INF;
for(int i = left; i < right; ++ i)
for(int j = left + 1; j <= right; ++ j)
ans = min(ans, Dist(p[i], p[j]));
return ans;
}
double Divide(int left, int right){
if(right - left < 2)
return BruteForce(left, right);
int mid = (left + right) >> 1;
double d = Divide(left, mid);
d = min(d, Divide(mid + 1, right));
int strip[n];
int j = 0;
for(int i = left; i <= right; ++ i)
if(abs(p[mid].x - p[i].x) < d)
strip[j ++] = i;
return min(d, StripClosest(strip, j, d));
}
int main(){
Read();
sort(p, p + n);
printf("%.10f\n", Divide(0, n - 1));
return 0;
}