Cod sursa(job #3339917)

Utilizator unomMirel Costel unom Data 10 februarie 2026 21:38:41
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <unordered_map>
#include <vector>

using namespace std;

#define int long long

struct pair_hash
{
    inline size_t operator()(const pair<int, int> &a) const {
        int x = a.first;
        int y = a.second;

        return (x * 31337) ^ (y * 1000000007);
    }
};

ifstream in("cmap.in");
ofstream out("cmap.out");
int n, d;
pair<int, int> v[100005];
unordered_map<pair<int, int>, vector<int>, pair_hash> mp;
int INF = (1LL << 60);

int dist(pair<int, int> a, pair<int, int> b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

void insert_point(int i)
{
    int x = v[i].first / d;
    int y = v[i].second / d;
    mp[{x, y}].push_back(i);
}

signed main()
{
    in>>n;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }


    d = sqrt(dist(v[1], v[2]));
    int ans = dist(v[1], v[2]);

    insert_point(1);
    insert_point(2);

    for(int i = 3; i<=n; i++)
    {
        int x = v[i].first / d;
        int y = v[i].second / d;

        int updated = 0;

        for(int dx = -1; dx<=1; dx++)
        {
            for(int dy = -1; dy<=1; dy++)
            {
                pair<int, int> key = {x + dx, y + dy};

                if(mp.find(key) != mp.end())
                {
                    for(auto it: mp[key])
                    {
                        int cur_d = dist(v[i], v[it]);

                        if(cur_d < ans)
                        {
                            ans = cur_d;
                            updated = 1;
                        }
                    }
                }
            }
        }

        if(updated == 1)
        {
            d = sqrt(ans);

            mp.clear();

            for(int j = 1; j<i; j++)
            {
                insert_point(j);
            }
        }
        insert_point(i);
    }

    long double rez = sqrt(ans);
    out<<setprecision(6)<<fixed<<rez;

    return 0;
}