Pagini recente » Cod sursa (job #3268670) | Romanii medaliati la IOI | Cod sursa (job #1393250) | Cod sursa (job #427119) | Cod sursa (job #3239774)
///the idea is dividing the sorted vector by x into 2 parts, using divide
///after dividing let's suppose the two halves have their point sorted by y
///to maintain this we just merge the 2 vectors with two pointers(interclasare)
///for the current segment we store the minimum length between two points from i, and the vectors with sorted point by y(it was sorted by x initially)
///let's denote d = min ((left, mid), (mid + 1, r))
///from the two halves we consider exclusively the points at most d distance from the center
///then for each half search in the other half a better distance with maximum like 10 points up or down
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>
#define double long double
using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");
const double MAX = (double)1e18;
const int N = 1e5;
struct point
{
int x, y;
} a[N + 1];
using pa = pair <double, vector<point> >;
int n, bulan = 10;
double dist (point a, point b)
{
return sqrt((double)((double)(a.x - b.x) * (double)(a.x - b.x) + (double)(a.y - b.y) * (double)(a.y - b.y)));
}
inline double ab (int x)
{
double y = (double)(x);
if (y < 0)return -y;
return y;
}
pa divide (int l, int r)
{
vector <point> aux;
if (l == r)
{
aux.push_back(a[l]);
return {MAX, aux};
}
int mid = (l + r) >> 1;
pa left_ans = divide (l, mid);
pa right_ans = divide (mid + 1, r);
double 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)
for (int j = i; j < min (i + bulan, (int)p2.size()); ++j)
d = min (d, dist(p1[i], p2[j]));
i = j = 0;
for (; i < p2.size(); ++i)
for (int j = i; j < min (i + bulan, (int)p1.size()); ++j)
d = min (d, dist(p2[i], p1[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};
}
int 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 (6) << divide (1, n).first << '\n';
return 0;
}