Pagini recente » Cod sursa (job #1443328) | Cod sursa (job #1328462) | Cod sursa (job #174405) | Cod sursa (job #527480) | Cod sursa (job #2189387)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
typedef pair <int, int> pii;
vector <pii> p;
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.second || (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;
vector <pii> v;
double ymid = (p[mid].first + p[mid+1].second)/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++)
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;
}