Pagini recente » Cod sursa (job #487212) | Cod sursa (job #2789048) | Istoria paginii runda/oji_2014_10/clasament | Cod sursa (job #1177337) | Cod sursa (job #2969242)
#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
{
ll x, y;
} v[100100], v2[100100];
deque<ll> squareCheck;
deque<ll>::iterator it;
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 (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
void mergeDist(int vst, int 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 (oldv[i].y > oldv[j].y)
swap(newv[i], newv[j]);
}
}
for (int i = vst; i <= vdr; i++)
maxx = max(maxx, int(oldv[i].x));
return;
}
int max1 = -INT_MAX, max2 = -INT_MAX, mij = (vst+vdr)/2, aux = mindist;
mergeDist(vst, mij, max1, newv, oldv);
mergeDist(mij+1, vdr, max2, newv, oldv);
maxx = max(max1, max2);
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 + aux) {
squareCheck.push_back(dr);
}
}
while (st <= vdr && oldv[st].y < oldv[j].y - aux) {
if (squareCheck.front() == st)
squareCheck.pop_front();
st++;
}
for (it = squareCheck.begin(); it != squareCheck.end(); advance(it, 1))
{
mindist = min(mindist, getDist(oldv[j], oldv[(*it)]));
}
}
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 = 0;
mergeDist(1, n, aux, v, v2);
g << std::fixed << setprecision(6);
g << sqrt(mindist);
f.close();
g.close();
return 0;
}