Pagini recente » Istoria paginii runda/pre004/clasament | Cod sursa (job #1893956) | Cod sursa (job #1966051) | Cod sursa (job #1719688) | Cod sursa (job #2495137)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
vector < pair <uint64_t, uint64_t> > v, w;
uint64_t dist (const pair <uint64_t, uint64_t>& a, const pair <uint64_t, uint64_t>& b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
uint64_t rec(int st, int dr)
{
if (dr - st <= 1) {return 0xffffff;}
if (dr - st == 2) {return dist(v[st], v[dr - 1]);}
if (dr - st == 3) {return max (dist(v[st], v[st+1]), max(dist(v[st], v[st+2]), dist(v[st+1], v[st+2])));}
int mid = (st + dr) / 2, i = st, j = mid, nr = st;
uint64_t ret = min(rec(st, mid), rec(mid, dr));
while (i < mid && j < dr)
{
if (w[i] < w[j]) {w[nr++] = v[i++];}
else {w[nr++] = v[j++];}
}
while (i < mid) {w[nr++] = v[i++];}
while (j < dr) {w[nr++] = v[j++];}
nr = 0;
mid = w[mid].first;
for (i = st; i < dr; ++i)
{
if (abs(v[i].second - mid) <= ret)
{
w[nr++] = v[i];
}
}
for (i = 0; i < nr - 1; ++i)
{
for (j = i + 1; j < nr && j - i < 8; ++j)
{
ret = min(ret, dist(w[i], w[j]));
}
}
return ret;
}
int main(void)
{
int n;
in >> n;
v.resize(n);
w.resize(n);
for (int i = 0; i < n; ++ i)
{
in >> v[i].first >> v[i].second;
}
in.close();
sort(v.begin(), v.end());
cout << sqrt(rec(0, n)) << "\n";
out.close();
return 0;
}