Pagini recente » Cod sursa (job #1174620) | Cod sursa (job #1904045) | Cod sursa (job #1755406) | Cod sursa (job #1674355) | Cod sursa (job #2769568)
#include <bits/stdc++.h>
#define NMAX 100005
#define ll long long
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
vector <pair <ll, ll>> P;
pair <ll, ll> R[NMAX];
ll dist(pair <ll, ll> a, pair <ll, ll> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
void interclasare(int st, int mid, int dr)
{
int i = st, j = mid + 1, k = st - 1;
while(i <= mid && j <= dr)
if(P[i].second < P[j].second)
R[++k] = P[i++];
else
R[++k] = P[j++];
for(; i <= mid; i++)
R[++k] = P[i];
for(; j <= dr; j++)
R[++k] = P[j];
for(int i = st; i <= dr; i++)
P[i] = R[i];
}
long long cmap(int st, int dr)
{
if(dr - st == 1)
{
interclasare(st, st, dr);
return dist(P[st], P[dr]);
}
if(dr - st == 2)
{
long long rez = min(dist(P[st], P[st + 1]), min(dist(P[st], P[dr]), dist(P[st + 1], P[dr])));
interclasare(st, st, st + 1);
interclasare(st, st + 1, dr);
return rez;
}
int mid = (st + dr) / 2;
long long rezSt = cmap(st, mid);
long long rezDr = cmap(mid + 1, dr);
interclasare(st, mid, dr);
long long rez = min(rezSt, rezDr);
for(int i = st; i < dr; i++)
for(int j = i + 1; j <= dr && j <= i + 7; j++)
rez = min(rez, dist(P[i], P[j]));
return rez;
}
int main()
{
f >> n;
for(int i = 1; i <= n; i++)
{
ll x, y;
f >> x >> y;
P.push_back(make_pair(x, y));
}
sort(P.begin(), P.end());
g << setprecision(7) << fixed << (long double)sqrt(cmap(1, n));
return 0;
}