Pagini recente » Cod sursa (job #862362) | Cod sursa (job #2999867) | Cod sursa (job #2965975) | Cod sursa (job #2476204) | Cod sursa (job #2969272)
#include <bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define ll long long
ll n, i, mindist = __LONG_LONG_MAX__;
struct Punct
{
int x, y;
} v[100100], v2[100100];
deque<int> squareCheck;
bool xComp(const Punct &a, const Punct &b)
{
if (a.x < b.x)
return true;
if (a.x == b.x)
if (a.y < b.y)
return true;
return false;
}
bool yComp(const Punct &a, const Punct &b)
{
if (a.y < b.y)
return true;
if (a.y == b.y)
if (a.x < b.x)
return true;
return false;
}
ll getDist(const Punct &a, const Punct &b)
{
return ((long long)(a.x - b.x)) * (a.x - b.x) + ((long long)(a.y - b.y)) * (a.y - b.y);
}
void mergeDist(ll vst, ll vdr, int &maxx, Punct *oldv, Punct *newv)
{
if (vst >= vdr-2) {
for (int i = vst; i < vdr; i++) {
for (int j = i+1; j <= vdr; j++) {
mindist = min(mindist, getDist(oldv[i], oldv[j]));
if (newv[i].y > newv[j].y)
swap(newv[i], newv[j]);
}
}
for (int i = vst; i <= vdr; i++)
maxx = max(maxx, oldv[i].x);
return;
}
int max1 = INT_MIN, max2 = INT_MIN;
ll mij = (vst+vdr)/2;
mergeDist(vst, mij, max1, newv, oldv);
mergeDist(mij+1, vdr, max2, newv, oldv);
maxx = max(max1, max2);
ll aux = mindist;
int st = mij+1;
int dr = mij;
for (int j = vst; j <= mij; j++) {
while (dr < vdr && oldv[dr+1].y <= oldv[j].y + aux) {
dr++;
if (oldv[dr].x <= max1 + mindist) {
squareCheck.push_back(dr);
}
}
while (st <= vdr && oldv[st].y < oldv[j].y - aux) {
if (!squareCheck.empty() && squareCheck.front() == st)
squareCheck.pop_front();
st++;
}
for (unsigned int k = 0; k < squareCheck.size(); k++)
{
mindist = min(mindist, getDist(oldv[j], oldv[squareCheck[k]]));
}
}
while (!squareCheck.empty())
squareCheck.pop_front();
int k = vst, i = vst, j = mij+1;
while (i <= mij && j <= vdr) {
if (oldv[i].y <= oldv[j].y) {
newv[k++] = oldv[i++];
}
else {
newv[k++] = oldv[j++];
}
}
while (i <= mij)
newv[k++] = oldv[i++];
while (j <= vdr)
newv[k++] = oldv[j++];
}
int main()
{
f >> n;
for (i = 1; i <= n; i++) {
f >> v[i].x >> v[i].y;
}
sort(v+1, v+n+1, xComp);
for (i = 1; i <= n; i++)
v2[i] = v[i];
int aux = INT_MIN;
mergeDist(1, n, aux, v, v2);
g << std::fixed << setprecision(6);
g << sqrt(mindist);
f.close();
g.close();
return 0;
}