Pagini recente » Cod sursa (job #2920588) | Monitorul de evaluare | Cod sursa (job #3282936) | Cod sursa (job #3137947) | Cod sursa (job #3293217)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
typedef long long ll;
ll d;
struct P{ll x, y;}v[1001];
bool cmp(P a, P b)
{
return a.x < b.x;
}
bool cmpY(P a, P b)
{
return a.y < b.y;
}
ll sq(ll a){return a*a;}
ll dist(P a, P b)
{
return (sq(a.x - b.x) + sq(a.y - b.y));
}
void solve(int st, int dr)
{
if(st == dr) return;
int mid = (st + dr) / 2;
int middle_x = v[mid].x;
solve(st,mid);
solve(mid+1,dr);
vector<P> stripe;
for(int i = st;i<=dr;i++)
if(sq(v[i].x - middle_x) <= d)
stripe.push_back(v[i]);
sort(stripe.begin(),stripe.end(),cmpY);
for(int i = 0;i<stripe.size();i++)
for(int j = i+1;j<stripe.size() && sq(stripe[i].y - stripe[j].y) < d;j++)
d = min(d, dist(stripe[i],stripe[j]));
}
int main()
{
int n;
cin >> n ;
for(int i = 1;i<=n;i++)
cin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
d = 1e18;
solve(1,n);
long double ans = sqrt(d);
cout << fixed<<setprecision(6) << ans << '\n';
return 0;
}