Pagini recente » Cod sursa (job #712016) | Cod sursa (job #3036717) | Cod sursa (job #431884) | Cod sursa (job #2397091) | Cod sursa (job #3239691)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>
#define int long long
using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");
const int MAX = 1e19;
const int N = 1e5;
struct point
{
int x, y;
} a[N + 1];
using pa = pair <int, vector<point> >;
int n;
int dist (point a, point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
inline int ab (int x)
{
if (x < 0)return -x;
return x;
}
pa divide (int l, int r)
{
vector <point> aux;
if (l > r)
return {MAX, aux};
if ((r - l) <= 2)
{
int d = MAX;
for (int i = l; i < r; ++i)
for (int j = i + 1; j <= r; ++j)
d = min (d, dist(a[i], a[j]));
for (int i = l; i <= r; ++i)
aux.push_back({a[i]});
sort (aux.begin(), aux.end(), [](const point &a, const point &b)
{
return a.y < b.y;
});
return {d, aux};
}
int mid = (l + r) >> 1;
pa left_ans = divide (l, mid);
pa right_ans = divide (mid + 1, r);
int d = min (left_ans.first, right_ans.first);
int center = a[mid].x;
vector <point> p1, p2;
for (auto it : left_ans.second)
if (ab (center - it.x) <= d)
p1.push_back(it);
for (auto it : right_ans.second)
if (ab(it.x - center) <= d)
p2.push_back(it);
///computed just the two vectors that are at diffrence less than the current optim
int i = 0, j = 0;
if (!p1.empty() && !p2.empty())
{
for (; i < p1.size(); ++i)
{
if (j == p2.size())
d = min (d, dist(p1[i], p2.back()));
while (j < p2.size() && ab(p2[j].y - p1[i].y) <= d)
d = min (d, dist(p1[i], p2[j])), ++j;
}
i = j = 0;
for (; i < p2.size(); ++i)
{
if (j == p1.size())
d = min (d, dist(p2[i], p1.back()));
while (j < p1.size() && ab(p1[j].y - p2[i].y) <= d)
d = min (d, dist(p2[i], p1[j])), ++j;
}
}
i = j = 0;
p1 = left_ans.second;
p2 = right_ans.second;
while (i < p1.size() && j < p2.size())
{
if (p1[i].y < p2[j].y)
aux.push_back(p1[i++]);
else if (p1[i].y > p2[j].y)
aux.push_back(p2[j++]);
else
{
aux.push_back(p1[i++]);
aux.push_back(p2[j++]);
}
}
while (i < p1.size())aux.push_back(p1[i++]);
while (j < p2.size())aux.push_back(p2[j++]);
return {d, aux};
}
signed main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].x >> a[i].y;
sort (a + 1, a + n + 1, [](const point &a, const point &b)
{
return a.x < b.x;
});
cout << fixed << setprecision (7) << (double)(sqrt(divide (1, n).first)) << '\n';
return 0;
}