Pagini recente » Cod sursa (job #357205) | Cod sursa (job #2608621) | Cod sursa (job #26016) | Cod sursa (job #1850994) | Cod sursa (job #2189407)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
typedef pair <int, int> pii;
const int NMAX = 100000;
pii p[NMAX+5];
double dist(pii a, pii b)
{
return sqrt(1LL*(a.first - b.first) * (a.first - b.first) +
1LL*(a.second - b.second) * (a.second - b.second));
}
bool cmp(pii a, pii b)
{
return a.first < b.first || (a.first == b.first && a.second < b.second);
}
bool cmp2(pii a, pii b)
{
return a.second < b.second || (a.second == b.second && a.first < b.first);
}
double solve(int st, int dr)
{
double Min = 1e13;
if(st == dr) return Min;
if(dr == st+1) return dist(p[st], p[dr]);
int mid = (st+dr)/2;
Min = min(solve(st, mid), solve(mid+1, dr));
vector <pii> v;
double ymid = (p[mid].first + p[mid+1].first)/2;
for(int i=mid; i>=st && abs(ymid - p[i].first) < Min; i--) v.push_back(p[i]);
for(int i=mid+1; i<=dr && abs(ymid - p[i].first) < Min; i++) v.push_back(p[i]);
sort(v.begin(), v.end(), cmp2);
for(int i=0; i<v.size(); i++)
for(int j=i+1; j<=i+4 && j<v.size(); j++)
Min = min(Min, dist(v[i], v[j]));
return Min;
}
int main()
{
fstream in("cmap.in");
fstream out("cmap.out");
int n;
in >> n;
for(int i=0; i<n; i++)
{
int x, y;
in >> x >> y;
p.push_back(pii (x, y));
}
sort(p.begin(), p.end(), cmp);
out << fixed << setprecision(12) << solve(0, n-1);
return 0;
}