Pagini recente » Istoria paginii utilizator/suranimaria_ | Diferente pentru preoji/clasament/9 intre reviziile 35 si 33 | Cod sursa (job #900764) | Cod sursa (job #1453856) | Cod sursa (job #2642743)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int nmax = 100000;
const long long inf = 9223372036854775807;
int n;
struct Point
{
long long x, y;
}v[nmax + 5], y[nmax + 5], aux[nmax + 5];
bool cmp(Point a, Point b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
long long dist(Point a, Point b)
{
return 1LL * abs(a.x - b.x) * abs(a.x - b.x) + 1LL * abs(a.y - b.y) * abs(a.y - b.y);
}
void interclaseaza(int st, int dr)
{
int mid = (st + dr) / 2;
int p1 = st, p2 = mid + 1, p3 = st;
while (p1 <= mid && p2 <= dr)
{
if (y[p1].y < y[p2].y)
{
aux[p3++] = y[p1++];
}
else
{
aux[p3++] = y[p2++];
}
}
while (p1 <= mid)
{
aux[p3++] = y[p1++];
}
while (p2 <= dr)
{
aux[p3++] = y[p2++];
}
for (int i = st; i <= dr; ++i)
{
y[i] = aux[i];
}
}
long long solve(int st, int dr)
{
if (dr - st + 1 <= 3)
{
interclaseaza(st, dr);
if (dr - st + 1 == 3)
{
long long minim = dist(v[st], v[st + 1]);
minim = min(minim, dist(v[st], v[dr]));
minim = min(minim, dist(v[st + 1], v[dr]));
return minim;
}
if (dr - st + 1 == 1)
{
return inf;
}
return dist(v[st], v[dr]);
}
int mid = (st + dr) / 2;
int x = v[mid].x;
long long minim = min(solve(st, mid), solve(mid + 1, dr));
interclaseaza(st, dr);
int p3 = 0;
for (int i = st; i <= dr; ++i)
{
if (1LL * abs(y[i].x - x) * abs(y[i].x - x) <= minim)
{
aux[++p3] = y[i];
}
}
for (int i = 1; i < p3; ++i)
{
for (int j = i + 1; j - i + 1 <= 8 && j <= p3; ++j)
{
minim = min(minim, dist(y[i], y[j]));
}
}
return minim;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> v[i].x >> v[i].y;
y[i] = v[i];
}
sort(v + 1, v + n + 1, cmp);
fout << setprecision(6)<< fixed << (double)sqrt(solve(1,n));
fin.close();
fout.close();
return 0;
}