Cod sursa(job #3239774)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 7 august 2024 15:50:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.08 kb
///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;
}