Pagini recente » Cod sursa (job #705665) | Cod sursa (job #2905653) | Cod sursa (job #1891707) | Cod sursa (job #2484605) | Cod sursa (job #1604402)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
int n;
struct Point {
int x, y;
Point(int xx, int yy){
x = xx;
y = yy;
}
};
vector<Point> p;
void readData(){
int x, y;
scanf("%d\n", &n);
for (int i = 1; i <= n; ++i){
scanf("%d %d\n", &x, &y);
p.push_back(Point(x, y));
}
}
double dist(Point A, Point B){
return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
double dist(Point A, int line){
return abs(A.x - line);
}
bool cmpXY(Point A, Point B){
return A.x < B.x || A.x == B.x && A.y < B.y;
}
bool cmpYX(Point A, Point B){
return A.y < B.y || A.y == B.y && A.x < B.x;
}
double dei(int st, int dr){
if (dr - st <= 3){
double mini = inf;
for (int i = st; i < dr-1; ++i)
for (int j = i+1; j < dr; ++j)
mini = min(mini, dist(p[i], p[j]));
return mini;
}
int mijl = (dr+st)/2;
double ps = dei(st, mijl);
double pd = dei(mijl, dr);
double pp = min(ps, pd);
/// pp
vector<Point> closeP;
closeP.clear();
for (int i = mijl-1; i >= 0 && dist(p[i], p[mijl].x) < pp; --i)
closeP.push_back(p[i]);
for (int i = mijl; i < dr && dist(p[i], p[mijl].x) < pp; ++i)
closeP.push_back(p[i]);
sort(closeP.begin(), closeP.end(), cmpYX);
for (int i = 0; i < closeP.size(); ++i)
for (int j = 1; j <= 7 && i+j < closeP.size(); ++j)
pp = min(pp, dist(closeP[i], closeP[i+j]));
return pp;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
readData();
sort(p.begin(), p.end(), cmpXY);
printf("%lf\n", dei(0, n));
return 0;
}